“我要将有关魔法和奇迹的一切,封印于卡片之中!”
“这个心愿„„要是这个心愿能够实现„„”
“对,这样你我都将化为卡片!”
现在,孵化者被封印在了一张卡片里。这张卡片的效果是:可以使一张魔法
卡片变为两张(可能是其他类型的)魔法卡片。显然,它是非常珍贵且有价值的
卡片。
我们接下来要关注的是一个以它为背景的,用于训练SpellCard的使用技巧,
以及:体现了孵化者无与伦比的再生能力的单人卡片游戏,叫做《Incubator》。
游戏的道具是一些卡片,分为两类,一类是 Spell,一类是 Witch。我们用大
写字母’A’、’B’、„„来表示不同的 Spell,用小写字母’a’、’b’、„„来表示不同
的 Witch。
游戏用到两个牌堆,我们称它们为 S 堆和 W 堆,S 堆中只可能有 Spell,W
堆中只可能有 Witch。
游戏开始时,S 堆仅有一张卡片’S’,而 W堆中会有若干张卡片,我们把这个
信息用一个字符串 w来表示,其中 w的首个字符对应 W堆顶部的卡片,w的下
一个字符对应 W堆从上向下数第二张卡片(如果有的话) ,依次类推。
游戏的目标是进行操作,使得这两个牌堆都变成空的,一共有两种操作:
1. 使用魔法消灭 Witch:
如果S 堆顶部的Spell克制 W堆顶部的 Witch 才可以进行。
使用后,这两张卡片都被移除。
2. 使用Incubator 进行孵化:
如果S 堆非空就可以进行。
需要依照某一孵化规则。
将S堆顶部的卡片移除, 由孵化规则在S堆顶部加入两张新的卡片。
这个游戏一共有N1个克制关系以及 N2个孵化规则。
每一个“克制”关系由一个字符串给出,例如: “A->a”表示’A’克制’a’。
每一个孵化规则也由一个字符串给出,例如: “S->AB” ,表示可以将’S’从堆
顶移除,之后加入’A’和’B’,其中’A’在’B’的上面。
在给定规则以及串 w的情形下,如果存在一个有限多步就可以使得两牌堆均
为空的操作方法,那么我们称:这个游戏是有解的。
你的任务是:给定规则以及 T个串:w1、w2、„„、wT,分别判定这个规则
和串所对应的游戏是否有解。