题目描述

1999年的世界总决赛比赛包括一个基于骰子迷宫的问题。在撰写问题时，评委们无法发现骰子迷宫概念的原始来源。然而，竞赛结束后不久，众多迷宫的创造者、该主题的作者罗伯特·阿伯特先生联系了竞赛评委，并确认自己是骰子迷宫的创始人。我们很遗憾，我们没有将雅培先生在过去几年的问题陈述中提出的最初概念归功于他。但我们很高兴地报告，艾伯特先生以其原创和未出版的《穿越箭头迷宫》为今年的比赛提供了他的专业知识。

与大多数迷宫一样，穿过箭头迷宫的方式是从交叉口移动到区间，直到到达目标交叉口。当从给定方向接近每个交叉口时，交叉口入口附近的标志指示可以从哪个方向退出交叉口。这些方向始终为左，向前或向右，或这些的任意组合。

图1显示了一个穿行箭头迷宫。交叉点被标识为（行、列）对，左上角为（1,1）。图1的入口交叉点为（3,1），目标交叉点为（3,3）。你从（3,1）向北移动开始迷宫。当你从（3,1）走到（2,1）时，（2,1）处的标志表明当你从南（向北）接近（2,1）时，你只能继续前进。继续前进会带你走向（1,1）。当你从南部接近时，（1,1）处的标志表明你只有向右才能离开（1,1）。这将使您现在向东从（1,1）向（1,2）行走。到目前为止，还没有做出任何选择。如果你继续从（1,2）移动到（2.2）到（2,3）到（1,3），情况也是如此。然而，现在，当你从（1,3）向西移动到（1,2）时，你可以选择继续直走或左转。继续直走会让你朝（1,1）走，而左转会让你向南走到（2.2）。该迷宫的实际（唯一）解决方案是以下交叉顺序：（3,1）（2,1）（1,1）（1.2）（2,2）（2.3）（1,3）（1,2）（1,1）（2,2）（1,2）（1,2）（1,2）（1,3）（1,3）。

您必须编写一个程序来解决有效的穿行箭头迷宫。解决迷宫意味着（如果可能的话）找到一条穿过迷宫的路线，使入口在规定的方向上，并到达目标。当然，这条路线的长度不应超过必要的长度。

输入格式

输入文件将由一个或多个箭头迷宫组成。每个迷宫描述的第一行包含迷宫的名称，它是一个不超过20个字符的字母数字字符串。下一行按以下顺序包含起始行、起始列、起始方向、goalrow，最后是goal列。所有字符都由一个空格分隔。对于这个问题，迷宫的最大尺寸是9乘9，因此所有行和列的编号都是1到9之间的单个数字。起始方向是N、S、E或W中的一个字符，分别表示北、南、东和西。

迷宫的所有剩余输入行都采用这种格式：两个整数、一组或多组字符和一个哨兵星号，所有这些都由一个空格分隔。整数分别表示迷宫交叉点的行和列。每个字符组表示该交叉点处的符号。组中的第一个字符是“N”、“S”、“E”或“W”，表示该标志在哪个方向行驶。例如，“S”表示这是向南行驶时看到的标志。（这是张贴在十字路口北口的标志。）在第一个方向字符之后是一到三个箭头字符。它们可以是“L”、“F”或“R”，分别表示左、前和右。交叉点列表由第一列中包含单个零的线结束。输入的下一行开始下一个迷宫，依此类推。输入的末尾是单行上的单词“end”。

输出格式

对于每个迷宫，输出文件应包含一行迷宫名称，后跟一行或多行迷宫解决方案或短语“不可能解决方案”。迷宫名称应从第1列开始，所有其他行应从第3列开始，即缩进两个空格。解决方案应以交叉点列表的形式输出，格式为（R，C），访问顺序为从起点到目标，并用一个空格分隔，除解决方案的最后一行外，其他所有行都应正好包含10个交叉点。

注:

罗伯特·阿伯特穿过箭迷宫实际上是为了大规模的建设，而不是纸上的。虽然他的迷宫没有出版，但有些已经出版了实际上已经建成了。其中一个在亚特兰大博物馆展出。其他人有由美国MazeCompany在过去两年夏天建造。像它们的名字表明，这些迷宫往往是步行穿过的。对于喜欢冒险的人来说，图2是罗伯特·阿伯特的亚特兰大迷宫的失写。解决它是相当困难的，即使在

你已经对整个迷宫有了一个大致的了解。想象一下，试图通过实际操作来解决这个问题穿过迷宫，一次只能看到一个标志！

罗伯特·艾伯特-赛尔夫表示，迷宫太复杂了，大多数人在离开之前就放弃了。在那些没有放弃的人中，有唐纳德·克努特：这让他付出了代价大约30分钟来解迷宫。

下面的示例输入中的第一个迷宫是MAZEIN图1。