迷宫游戏是在一张 n×m的网格图中进行的,其中 a _{i,j}表示第 i 行、第 j 列网格的状态,每个网格有以下
4 种情况:
若a _{i,j} 为 . ,则表示该位置为可以走的空地
若a _{i,j}为 # ,则表示该位置为不可走的墙壁
若a _{i,j} 为 1 ,则表示该位置为小爱初始的位置
若a _{i,j}为 2 ,则表示该位置为小艾初始的位置
每一轮游戏开始时,可以自由决定是小爱先移动还是小艾先移动,他们可以移动至相邻的上下左右四个空格或原地不动,但又不可以移动至对方所在的网格中。
请问,游戏最少进行多少轮,才能使小爱和小艾互换位置?
输入第一行,两个正整数分别表示 n,m
接下来的第 2 行至第 n+1 行,每行 m 个字符,其中第 i+1 行、第 j 列的字符表示初始时网格 a _{i,j}的状态。
输出共一行,一个整数表示两人互换位置最少需要的轮数,若无法完成,则输出 No Solution
。
3 3 1.. ... ..2
4
2 3 1.2 #.#
4
3 3 1.# #.# #.2
No Solution
对于 50%50%的数据,1≤�,�≤51≤n,m≤5
对于 100%100%的数据,1≤�,�≤301≤n,m≤30
样例2解释:
1.2 .12 .2. 21. 2.1
#.# --> #.# --> #1# --> #.# --> #.#
时间限制 | 1 秒 |
内存限制 | 128 MB |