题目详情
返回题库题目描述
迷宫游戏是在一张 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) 的状态。
数据范围
- 对于 50%的数据，1≤n,m≤5
- 对于 100%的数据，1≤n,m≤30
输出描述
输出共一行，一个整数表示两人互换位置最少需要的轮数，若无法完成，则输出No Solution。