Abbott的复仇 Abbott's Revenge
题意翻译
给出一个箭头迷宫,在每个路口处,如果你从某个方向进入了该路口,那么路口的地面上在靠近你的方向会画有一组箭头,它们相对于你的方向可以是向左,向前,向右,或者是它们的任意组合。
当你从某一方向进入某个入口时,下一步只能在这个入口对应方向上标记的箭头中选一个方向继续行进。在起点时,可以选择任何方向。
给出起点和终点,求它们之间的最短路径。
每条边的长度为1
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=757
[PDF](https://uva.onlinejudge.org/external/8/p816.pdf)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA816/815d09b7103ad071de9d9f7869315aa2585ea85b.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA816/4939e773b1884a681cdc9dbd1fe1251df58b072b.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA816/9ff2bb3a862e6ca3e356ecb98a558f994c9d7f5d.png)
输入输出样例
输入样例 #1
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
Figure 1: An Example Walk-Through
Arrow Maz
输出样例 #1
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