问题描述

Acm 是一位寻宝者，他又开始探索了。这一次他在一个特殊的迷宫里，里面有一些门（最多5扇门，分别用 $A$、$B$、$C$、$D$、$E$ 代表）。为了找到宝藏，Acm 可能需要打开门。然而，要打开一扇门，他需要先在迷宫中找到所有门的钥匙（至少一把）。例如，如果门 $A$ 有 3 个钥匙，要打开门，他应该先找到所有 3 个钥匙（即三个“$a$”，表示迷宫中“$A$”的钥匙）。现在制作一个程序告诉 Acm 他是否能找到宝藏。请注意，Acm 在迷宫中只能向上、向下、向左和向右移动。

输入

输入由多个测试用例组成。每个测试用例的第一行包含两个整数 $M$ 和 $N$（$1 < N、M < 20$），表示迷宫的大小。接下来的 $M$ 行给出了迷宫布局，每行包含 $N$ 个字符。字符是以下字符之一：

• “$X$”（一块墙，探险者无法进入）
• “$.$”（空块）
• ‘$S$’ （Acm 的起点）
• ‘$G$’ （宝藏的位置）
• ‘$A$’、‘$B$’、‘$C$’、‘$D$’、‘$E$’ （门）
• ‘$a$’、‘$b$’、‘$c$’、‘$d$’、‘$e$’ （门的钥匙）

input 以两个 $0$ 终止。不应处理此测试用例。

输出

对于每个测试用例，如果 Acm 可以找到宝藏，则在一行中输出 “YES” ，否则输出 “NO”。

输入数据 1

4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0

输出数据 1

YES
NO

源于

POJ 月刊，王一杰