#BZOJ2664. 孵化者

孵化者

No submission language available for this problem.

题目描述

“我要将有关魔法和奇迹的一切,封印于卡片之中!”
“这个心愿„„要是这个心愿能够实现„„”
“对,这样你我都将化为卡片!”
 
现在,孵化者被封印在了一张卡片里。这张卡片的效果是:可以使一张魔法
卡片变为两张(可能是其他类型的)魔法卡片。显然,它是非常珍贵且有价值的
卡片。
 
我们接下来要关注的是一个以它为背景的,用于训练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,分别判定这个规则
和串所对应的游戏是否有解。

输入格式

第一行一共有两个正整数:N1、N2。
接下来 N1行,每行一个串,表示一个克制关系。
接下来 N2行,每行一个串,表示一个孵化规则。
接下来 T 行,每行一个串 wi。 

输出格式


一共输出 T行:
每行为“YES”或“NO”(不包含引号),表示对应的串和规则组成的游戏是
否是有解的。(有解则输出“YES”,否则输出“NO”)


2 1
A->a
B->b
S->AB
ab
cd
YES
NO

数据范围与约定

对于100%的数据: 1≤  N1≤20, 1 ≤  N2≤20, 1 ≤  |wi|≤  20, 1≤  T≤100。

保证所有的克制关系串都是合法的,即具有“A->a”的形式,其中 A 是某

个大写字母,a 是某个小写字母。

保证所有的孵化规则串都是合法的,即具有“S->AB”的形式,其中 S、A、

B是某些大写字母,它们可以相同。

“->”是一个长度为 2 的串,其首个字符的 ASCII 码为 45,下一个字符的

ASCII 码为62 (均是在十进制下) ,这个符号也是 C++中的 Structure dereference。

保证串 wi仅包含小写字母。