开始: 2024-04-22 00:00:00

(23-24赛季)稠州常规赛12

结束: 2024-04-25 00:00:00
当前  2025-01-24 18:01:52  类型: IOI  状态: 已经结束 

P6. 位置互换
描述

迷宫游戏是在一张 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≤�,�≤51n,m5

  • 对于 100%100%的数据,1≤�,�≤301n,m30

样例2解释:

1.2          .12           .2.          21.        2.1

#.#  -->  #.#  -->  #1#  -->  #.#   -->  #.#  


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交