Description

有一个最多包含9*9个交叉点的迷宫。输入起点、离开起点时的朝向和终点，求一条最短路

Input Format

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

迷宫的所有剩余输入行都具有以下格式：两个整数、一组或多组字符和一个哨兵星号，同样全部由单个空格分隔。整数表示迷宫交叉点的行和列。每个字符组在那个交叉点代表一个符号。该组中的第一个字符是"N"、"S"、"E"或"W"，以指示该标志将在哪个方向上被看到。例如，"S"表示这是当向南旅行时看到的标志。（这是十字路口北侧入口处的标志。）在第一个方向后面是一到三个箭头字符。它们可以分别是"L"、"F"或"R"，分别表示左、前、右。

交叉路口的列表由第一列中包含一个零点的线结束。输入的下一行开始下一个迷宫，以此类推。输入的末尾是一行单行上的“结束”一词。

Output Format

对于每个迷宫，输出文件应该包含一行带有迷宫的名称，后面跟着一行或多行带有迷宫的解决方案或短语“不可能的解决方案”。迷宫名称应该从第1列开始，所有其他行都应该从列3开始，即缩进两个空格。解决方案应该以格式(R,C)作为交叉点列表输出，按照从开始到目标访问它们的顺序，应该用一个空格进行分隔，并且除了解决方案的最后一行之外，所有的解决方案都应该精确地包含10个交叉点。

SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END​

SAMPLE
  (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)
NOSOLUTION
  No Solution Possible​

Source

搜索