#823. 国庆第四题
国庆第四题
背景:
“吃电脑公会”正在探索一座神秘的虚拟迷宫。公会的每个成员都希望找到从迷宫起点到终点的最短路径。迷宫由一个二维矩阵表示,其中0
代表可以通过的道路,1
代表无法通行的墙壁。起点位于左上角((0,0)
),终点位于右下角((n-1, m-1)
)。公会需要你编写一个程序,帮助他们找到从起点到终点的最短路径长度。
题目描述:
给定一个n x m
的二维矩阵maze
,表示迷宫的地图。你的任务是找到从起点 (0,0)
到终点 (n-1,m-1)
的最短路径的步数。如果无法到达终点,则返回 -1
。
你可以向上、下、左、右四个方向移动,但不能移动到迷宫外,也不能穿过墙壁(即值为 1
的位置)。
输入格式:
- 第一行包含两个整数
n
和m
,表示迷宫的行数和列数(1 <= n, m <= 100
)。 - 接下来的
n
行,每行包含m
个整数,表示迷宫的结构。0
代表道路,1
代表墙壁。
输出格式:
- 输出一个整数,表示最短路径的长度。如果无法到达终点,返回
-1
。
示例:
输入:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
1 1 1 1 0
0 0 0 0 0
输出:
9
说明:
- 在这个例子中,最短路径是
(0,0) -> (1,0) -> (2,0) -> (3,0) ->(4,0) -> (4,1) -> (4,2) -> (4,3) -> (4,4)
,一共9步。
提示:
- 使用广度优先搜索(BFS)算法可以高效地解决迷宫最短路径问题。
- 可以利用队列来存储每一步的状态,并记录当前位置的步数。
- 如果在遍历过程中遇到终点
(n-1, m-1)
,直接输出当前步数。 - 注意边界条件的判断以及如何处理无法到达终点的情况。
解题思路:
- 初始化一个队列,将起点
(0,0)
和当前步数1
加入队列。 - 在队列不为空时,取出当前节点并检查四个方向的相邻节点是否可以移动:
- 如果可以移动,且未被访问过,将该节点加入队列,并标记为已访问。
- 如果到达终点
(n-1, m-1)
,则输出当前步数。
- 如果队列为空且没有找到终点,输出
-1
。
相关
在下列比赛中: