迷宫最短步数

题目描述

给定一个 (n \times m) 的迷宫，迷宫中每个位置可能是空地或墙。

• . 表示该位置可以通行；
• # 表示该位置不能通行。

小明从迷宫左上角 ((1, 1)) 出发，想要走到右下角 ((n, m))。

小明每一步只能向 上、下、左、右 四个方向移动一格，不能走出迷宫，也不能走到墙上。

请你计算小明从起点 ((1,1)) 到终点 ((n,m)) 至少需要经过多少个格子。

如果无法到达终点，输出 -1。

注意：起点也算作第 1 步。

---

输入格式

第一行输入两个整数 (n, m)，表示迷宫的行数和列数。

接下来 (n) 行，每行输入 (m) 个字符，表示迷宫。

字符只可能是：

• .：可以通行；
• #：不可通行。

---

输出格式

输出一个整数，表示从 ((1,1)) 到 ((n,m)) 的最少步数。

如果无法到达终点，输出：

-1

---

数据范围

1 ≤ n, m ≤ 100

迷宫中的字符只包含 . 和 #。

---

输入样例 1

3 4
....
.##.
....

输出样例 1

6

样例解释 1

一种最短走法为：

(1,1) → (1,2) → (1,3) → (1,4) → (2,4) → (3,4)

一共经过 6 个格子，所以输出：

6

---

输入样例 2

3 3
.#.
###
...

输出样例 2

-1

样例解释 2

起点在左上角，终点在右下角，但中间被墙阻挡，无法到达终点，所以输出：

-1

---

输入样例 3

1 1
.

输出样例 3

1

样例解释 3

起点和终点是同一个位置，并且该位置可以通行。

起点也算作第 1 步，所以输出：

1

---

输入样例 4

2 2
#.
..

输出样例 4

-1

样例解释 4

起点 ((1,1)) 是墙，不能通行，因此直接输出：

-1

---