编程介的小学生 2020-01-16 11:58 采纳率: 20.5%
浏览 144

Worms 请问怎么做

Problem Description
Biologists are studying a certain, interesting kind of worm. Each worm can be seen as a line of cells of different types. When a worm is born, it only consists of a single cell. Every day, exactly 1 cell of the entire worm will grow and change into 2 cells. It is rather easy to determine the age of any such worm, since it's simply one less than the number of cells the worm has.

During a worm's growth, a cell does not change into any 2 arbitrary cells; each worm has a set of ``growth rules" (encoded in its DNA) that it obeys. A growth rule can be expressed as A --> BC , where A , B and C are uppercase letters (with letters A-T), representing different types of the worm's cells. The rule A --> BC means that in one day, any single cell A can be grown into the 2 adjacent cells BC , in that order. Note that the rule I --> JK is different from the rule I --> KJ . Different worms may have a different set of growth rules.

The worms have now thrown the scientists for a loop. Due to some unknown reason, some worms have mutated into a new kind of specimen. This new kind of worm has the exact same properties, except that during its growth, multiple parts of its body can grow at the same time. That is, every day any (at least one, at most all) of its cells can grow; each cell that grows will grow into exactly 2 cells (obeying growth rules similar to their older cousins).

As a result of the mutation, it is no longer trivial to determine the age of a worm. In fact, the exact age of some worms cannot be determined. As a simple example, if a worm has growth rules: A --> BC , B --> AC , C --> AB , and the worm's current cell structure is ACAB , the worm can be either 2 or 3 days old ( A --> BC --> ACAB , or A --> BC --> ACC --> ACAB ). Your task is to find out the youngest possible age of any given mutated worm.

Input
There will be multiple worms for examination in the input. Each worm's data set begins with an integer N ( 1<=N<=80 ), the number of growth rules. The next N lines each contain 3 uppercase letters (with letters A-T), representing a growth rule for the current worm. The 1st cell can grow into (and be replaced by) the 2nd and 3rd cells, in order, during the growth process. That is, the line:

ABC

means A --> BC is a growth rule for the current worm.

The next (and last) line of each worm's data set contains a string of uppercase letters (with letters A-T). This line represents the current cell structure of the worm. Every worm in the input will have at least 1 and at most 50 cells.

The last worm will be followed by a line with a single 0.

Output
For each worm, if the worm can be grown into the given cell sequence with the given growth rule set (starting with any arbitrary single cell), then print the minimum age, in days, of the worm, as an integer on its own line. If the worm cannot be grown into the given cell sequence with the given rule set (starting with any arbitrary single cell), then simply print the number `-1' on its own line. Print no blank lines between outputs.

Sample Input
3
ABC
BAC
CAB
ACAB
1
AAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
2
PAA
AAA
AAAAAAAAAAAAAAAP
1
BAB
AAAAAAB
0

Sample Output
2
6
-1
6

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥100 有人会搭建GPT-J-6B框架吗?有偿
    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名