荷兰信息学奥林匹克 2025-2026 第一轮

A5. 甜甜圈迷宫（Donut doolhof）

原赛事： Nederlandse Informatica Olympiade 赛季： 2025-2026 阶段： 第一轮（Eerste ronde）

---

题目描述

下面的图中展示了一个迷宫示例，这个迷宫有 (R) 行、(K) 列。

任务是让老鼠 M 用尽可能少的步数到达甜甜圈 D。

迷宫示例：

o o o # # # o # #
# M o # o o # o #
# o # o # o # # o
# o o o o # o o o
o # o o o # # D o
o o o # # o # o o

其中：

• M 表示老鼠；
• D 表示甜甜圈；
• o 表示可以通过的格子；
• # 表示不能通过的格子。

---

移动规则

老鼠每次可以进行一次：

• 竖直移动：向上或向下移动一格；
• 水平移动：向左或向右移动一格。

标有 # 的格子不能进入。

标有 o 的格子可以进入。

---

特殊规则：迷宫首尾相连

这个迷宫有一个特殊之处：

你可以一直向某个方向走，不会走出迷宫。

具体来说：

• 如果你位于最上面一行，再向上走一步，就会来到最下面一行的同一列；
• 如果你位于最右边一列，再向右走一步，就会来到最左边一列的同一行；
• 向左越过最左边界时，同样会来到最右边；
• 向下越过最下边界时，同样会来到最上边。

也就是说，这个迷宫的上下边界、左右边界都是相连的。

---

输入格式

编写一个程序，从标准输入读取：

第一行包含两个整数：

R K

其中：

$$1<R\le900$$ $$1<K\le900$$

两个整数之间用一个空格分隔。

接下来输入 (R) 行，每行包含 (K) 个字符，表示整个迷宫。

---

输出格式

程序向标准输出输出一行：

老鼠从 M 到甜甜圈 D 的最短路径所需要的步数。

如果甜甜圈无法到达，则输出：

0

程序时间限制为：

1 秒

---

样例

输入：

6 9
ooo###o##
#Mo#oo#o#
#o#o#o##o
#oooo#ooo
o#ooo##Do
ooo##o#oo

输出：

6

---

样例说明

原题说明中给出了一条长度为 6 的可行路线。

其中：

• 第 2 步从最上面一行越过上边界，移动到了最下面一行的同一列；
• 第 4 步从最左边一列越过左边界，移动到了最右边一列的同一行。

因此最短距离为：

6