2022.2.9
题目网址：
http://noi.openjudge.cn/ch0205/1159/
原题：
Maze
总时间限制:
2000ms
内存限制:
65536kB
描述
Acm, a treasure-explorer, is exploring again. This time he is in a special maze, in which there are some doors (at most 5 doors, represented by 'A', 'B', 'C', 'D', 'E' respectively). In order to find the treasure, Acm may need to open doors. However, to open a door he needs to find all the door's keys (at least one) in the maze first. For example, if there are 3 keys of Door A, to open the door he should find all the 3 keys first (that's three 'a's which denote the keys of 'A' in the maze). Now make a program to tell Acm whether he can find the treasure or not. Notice that Acm can only go up, down, left and right in the maze.
输入
The input consists of multiple test cases. The first line of each test case contains two integers M and N (1 < N, M < 20), which denote the size of the maze. The next M lines give the maze layout, with each line containing N characters. A character is one of the following: 'X' (a block of wall, which the explorer cannot enter), '.' (an empty block), 'S' (the start point of Acm), 'G' (the position of treasure), 'A', 'B', 'C', 'D', 'E' (the doors), 'a', 'b', 'c', 'd', 'e' (the keys of the doors). The input is terminated with two 0's. This test case should not be processed.
输出
For each test case, in one line output "YES" if Acm can find the treasure, or "NO" otherwise.
翻译：
描述：
Acm，一个宝藏探索者，正在又一次探索宝藏。这次他在一个专门的迷宫里，这个迷宫里有一些门（最多5扇门，分别为‘A’，‘B’，‘C’，‘D’，‘E’）。为了找到宝藏，Acm可能需要去打开这些门。然而，为了打开这些门他首先需要找到在这个迷宫里的所有门的钥匙（至少一把）。例如，如果这里有三把‘A’门的钥匙，为了打开这个门他首先应该找到所有的这3把钥匙（三个‘a’代表这个迷宫里的3把‘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’（门相对应的钥匙）。输入以两个0结束。这个测试样例应该没有被处理过。
输出：
对于每组测试样例，如果Acm能找到宝藏，那么输出一行“YES”，否则输出“NO”。