5466 - Abbott’s Revenge

在1999年的World Finals中有一个基于Dice Maze(骰子迷宫)的题目。在出题人编写那道题目的时候，他们并没有发现这种迷宫的创意来源。然而在那场比赛结束不久，创作了大量的这种迷宫的Robert Abbott先生，联系了比赛主办方并确认自己是骰子迷宫的原作者。我们很遗憾没有在去年的题目描述中感谢Abbott先生的原创意，但我们很高兴Abbott先生主动为今年的比赛提供他原创的、未公开的“步行通过的箭头迷宫”。
　　与大多数的迷宫相同，箭头迷宫也是每次从一个路口走到另一个路口，直到到达终点。在每个路口处，如果你从某个方向进入了该路口，那么路口的地面上在靠近你的方向会画有一组箭头，它们相对于你的方向可以是向左，向前，向右，或者是它们的任意组合。
　　图1描述了一个箭头迷宫。每个路口用二维坐标(x,y)表示，以左上角的路口为(1,1)。在图1给出的迷宫中，起点的坐标是(3,1)，终点的坐标是(3,3)。在你开始后，你只能向北走1步到达(2,1)。由于你是从南边到达(2,1)这一点的，而这一点在南边的箭头是向前指的，所以你只能继续向前走到达(1,1)。在此之后，由于你是从南边到达了(1,1)，这一点在南边的箭头是向右指的，所以你也只能向右拐，到达(1,2)。到目前为止，你还没有做出任何选择。以此类推，你会接着依次经过(2,2) (2,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,1) (2,2) (1,2) (1,3) (2,3) (3,3)。
　　你需要写一个程序解决这个迷宫。“解决”的意义是：只要迷宫是可解的，你就要找到一条路线，它必须在起点沿指定的方向走出，并最终到达终点，当然，路线的长度需要是所有方案中最短的。

输入文件包括一个或多个箭头迷宫。每个迷宫描述的第一行是这个迷宫的名称，保证它只由数字和字母组成且长度不超过20。接下来的一行依次包含了起点的坐标，起始时方向，目标点的坐标，以空格隔开。本题的迷宫最大尺寸为9×9，所以行与列的编号均为1到9。起始时的方向为N,S,E,W之一，分别代表北、南、西、东。
　　剩下的若干行按照以下格式输入：一对整数，若干字符串，以星号(*)结束，以空格隔开。每一行代表一个路口，一对整数表示路口的坐标。对于每一个字符串，第一位为N,S,E,W之一，接下来若干位只可能包含L,F,R，分别代表向左，向前，向右。这个字符串的含义是：朝向某个方向进入该路口(所以箭头被画在这个路口的相反方向)，接下来就只能向某个方向继续行走。
　　对于每个迷宫，以0作为一行的结束，从接下来一行开始就是一个新的箭头迷宫。输入文件以单独的一行END作为结尾。

对于每个箭头迷宫，应该先输出它的名字，然后接下来若干行，输出一个路径，格式如问题描述中所述；或者输出"No Solution Possible"。迷宫的名字应从第1列开始，而其余所有的行都从第3列开始，即行首有2个空格。对于输出的每个路径，除最后一行外，每行须输出恰好10个路口(坐标)。
　　在下面的样例中，输入的第一个迷宫是图1中的迷宫。
　　注意，在下面的样例输出当中，除了SAMPLE和NOSOLUTION两行以外，其余的行首都需要空两格！（由于格式化问题未能显示出来）

数据规模和约定

　　设T为数据组数：对于30%的数据，T=1；对于60%的数据，T≤100；对于100%的数据，T≤1000。

蓝桥杯