迷宫
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
迷宫
题目描述
一个迷宫由 行 列的格子组成,有的格子里有障碍物,不能通行;有的格子是空地,可以通行。
给定一个 大小的迷宫,空地格子用 . 表示,有障碍物的格子用 # 表示。
求从左上角(第 行第 列)走到右下角(第 行第 列)最少需要走多少步。每步只能向上、下、左、右四个方向移动一格,不能斜着走,也不能走出迷宫或进入障碍物。
数据保证起点、终点均为空地,且一定存在从起点到终点的路径。若起点和终点是同一个格子,则答案为 。
输入格式
第一行包含两个整数 ,分别表示迷宫的行数和列数。
接下来 行,每行包含一个长度为 的字符串,仅由 . 和 # 组成,表示迷宫。
输出格式
输出一个整数,表示从左上角走到右下角的最少步数。
样例 1
3 3
...
.#.
...
4
样例 2
1 1
.
0
数据范围与提示
对于本题所提供的测试数据:,并且 。
- 每走到相邻的一格计为 步,起点不计步数。
- 数据保证可以走到终点。
- 建议使用**广度优先搜索(BFS)**求无权网格图的最短路;普通 DFS 不保证在大数据下能及时找到最短路。