主页 讨论版 问题 名次 状态 统计
问题 L: 营救公主

问题 L: 营救公主

时间限制: 1 Sec  内存限制: 128 MB
提交: 158  解决: 38
[提交][状态][讨论版]

题目描述

DSKer今天又做梦了,他的睡眠质量一直很差。他梦见他化身骑士(不存在),去营救公主。
公主被困在一个迷宫里。迷宫里有N个编过号的门(N<=5),它们分别被编号为A,B,C,D,E.为了救出公主,DSKer必须打开门,但是,开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙(每个门都至少有一把钥匙),例如:现在A门有三把钥匙,DSKer就必须找全三把钥匙才能打开A门。
现在请你编写一个程序来告诉DSKer,他能不能顺利救出公主。

输入

多组测试数据。
每组测试数据的第一行包含了两个整数M,N(1<N,M<=20),分别代表了迷宫的行和列。接下来的M每行有N个字符,描述了迷宫的布局。其中每个字符的含义如下:
.表示可以走的路
S:表示DSKer的出发点
G表示公主的位置
X表示这里有墙,DSKer无法进入或者穿过。
A,B,C,D,E表示这里是门,a,b,c,d,e表示对应大写字母的门上的钥匙。
注意DSKer只能在迷宫里向上下左右四个方向移动。
最后,输入0 0表示输入结束。

输出

每组数据输出一个YES表示DSKer能救出公主,输出NO表示他不能救出公主。

样例输入

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

样例输出

YES 
NO

提示

[提交][状态][讨论版]