SP2053 CERC07K - Key Task

有一个二维的迷宫，每一个方格中可能会有墙、可通行的路、门或钥匙。门和钥匙各有四种颜色：蓝色（Blue），黄色（Yellow），红色（Red）和绿色（Green）。一把钥匙只能打开与其颜色相同的门。 注意：你不能对角线移动；不能穿过墙壁；不能走出迷宫的区域；当你碰到一扇门时，手上必须有与其相同颜色的钥匙方可通过。 现在给出迷宫与当前你所处的位置，求出走出迷宫最少需几步。

输入若干个组数据，第一行是迷宫的长宽$R$和$C$。紧接着的$R$行，每行包含$C$个字符。下面是字符的种类： 井号$'$#$' $ 表示墙； 点$'.'$ 表示道路； 星号$'*'$ 表示你的起始位置； 大写字母$'B'$，$'Y'$，$'R'$，$'G'$ 分别表示蓝色、黄色、红色和绿色的门； 小写字母$'b'$，$'y'$，$'r'$，$'g'$ 分别表示蓝色、黄色、红色和绿色的钥匙； 大写字母$'X'$ 表示出口。 请注意，数据允许： - 多个出口 - 没有出口 - 多扇相同颜色的门或多把相同颜色的钥匙 - 没有对应某扇门的钥匙或对应某把钥匙的门 每个迷宫中$'*'$只会出现一次，输入以两个$0$结束。

对于每个迷宫，若可以走出，输出"Escape possible in S steps."，句子中的$S$表示最小的步数，否则输出"The poor student is trapped!"。拾取钥匙或打开门不计入步数。 感谢@Silvester 提供的翻译