問題文
高桥喜欢迷宫。我目前正在尝试在可以上下左右移动的二维板上解决迷宫。董事会的格式如下:
- 首先,您会得到棋盘的大小以及迷宫起点和终点的坐标。
- 接下来,每个方格可以穿过一个空方格(
.)或不可通行的墙壁空间(#))。棋盘周围有方块墙。起点和目标点始终是空的方块,并且您始终可以沿着空的方块从起点到达目标点。具体来说,最好参考输入/输出示例。
现在他想找到解决上述迷宫所需的最少步数。当我研究如何找到它时,我了解到一种称为“广度优先搜索”的方法是有效的。广度优先搜索是以下方法。
- 从距离起点最近的方格(到达起点所需的最短移动次数)开始,按如下方式确定到达起点所需的移动次数。我们将使用图 1 中的迷宫作为说明性示例。

- 首先,从起点出发可以用0步(当然)到达起点,所以以最短的步数(0)来确定(图2)。

- 接下来,一步确定起点附近的四个空位(上、下、左、右)(图3)。

- 接下来,查看第 1 步中确定的每个方格的四个邻居,如果还有尚未确定的空方格,请在第 2 步中确认该方格(图 4)。

- 接下来,查看 2 步确定的每个方格的 4 个邻居,如果有尚未确定的空方格,则通过 3 步确认该方格(图 5)。

- 接下来,查看3步确定的每个方格的4个邻居,如果有尚未确定的空方格,则在4步中确认该方格(图6)。

- 通过重复上述过程,直到不再有确认的更新,将确定从起点可以到达的所有空方格的最短移动次数(图7)。由于有一个限制,即您始终可以沿着空方块到达起点和目标,因此您还可以知道到达目标的最短步数。

现在,为了巧妙地实现这个过程,我们知道最好使用一种称为先进先出(FIFO)队列的数据结构。当然,不使用它也可以解决问题。这次,如果您不明白问题,我们建议您尝试使用您想出的方法来解决它。先进先出队列是一种数据结构,具有以下功能:
- 推送:将数据添加到队列末尾。
- Pop:取出队列头部的数据。
使用这种数据结构,您可以看到,通过在前面广度优先搜索的说明中“确定方格的最短移动次数”时将确认的方格添加到队列中,在添加操作完成时执行 Pop,并检查提取的方格的四个邻居(换句话说,从最先添加的方格开始按顺序处理),可以轻松完成处理。
入力
输入将以以下格式从标准输入给出。
R\ C
sy\ sx
gy\ gx
c_{(1,1)}c_{(1,2)}\ …\ c_{(1,C)}
c_{(2,1)}c_{(2,2)}\ …\ c_{(2,C)}
:
c_{(R,1)}c_{(R,2)}\ …\ c_{(R,C)}
- 1 行号是 R(1≦R≦50)和列数 C(1≦C≦50)用空格分隔。
- 2 行包含起点的坐标。 (sy,sx) 用空格分隔。起点是 sy 行 sx 列。 1≦sy≦R 和 1≦sx≦C 。
- 3 行包含目标点的坐标。 (gy,gx) 用空格分隔。目标点是 gy 行 gx 列。 1≦gy≦R 和 1≦gx≦C 和(gy,gx)≠(sy,sx)有保证。
- 4 在 R 线,长度
字符串 C 是 1 逐行给出。每个字母都是
.或#,以及 赋予i 回目 (1≦i≦R) 的字符串 对于 j 文字目 (1≦j≦C) ,字符是.然后质量 (i,j) 是一个空方块,#然后质量 (i,j) 表示它是一个墙方块。 - 棋盘被墙方块包围。换句话说,i=1,i=R,j=1,j=C 满足任意一个条件的方格 (i,j) ,c_{(i,j)} 为
#。另外,起点和目标点始终是空的方块,并且您始终可以从起点沿着空的方块到达目标点。
出力
- 从起点移动到目标点的最小移动次数 在 1 行输出。不要忘记最后的换行符。
入力例1
7 8 2 2 4 5 ######## #......# #.###### #..#...# #..##..# ##.....# ########
出力例1
11
这是问题文本中的示例。
入力例2
5 8 2 2 2 4 ######## #.#....# #.###..# #......# ########
出力例2
10
如果按照图 8 所示继续操作 10 你可以通过伸手前进(*S代表开始,G代表目标)。

入力例3
50 50 2 2 49 49 ################################################## #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# ##################################################
出力例3
94
现在只是一片宽阔的空间,不知道是否可以称之为迷宫,但对于这个问题,像这样的木板也会被视为迷宫。在这两种情况下,从起点到目标的最短步数是 94 。