#823. 国庆第四题

国庆第四题

背景:

“吃电脑公会”正在探索一座神秘的虚拟迷宫。公会的每个成员都希望找到从迷宫起点到终点的最短路径。迷宫由一个二维矩阵表示,其中0代表可以通过的道路,1代表无法通行的墙壁。起点位于左上角((0,0)),终点位于右下角((n-1, m-1))。公会需要你编写一个程序,帮助他们找到从起点到终点的最短路径长度。

题目描述:

给定一个n x m的二维矩阵maze,表示迷宫的地图。你的任务是找到从起点 (0,0) 到终点 (n-1,m-1) 的最短路径的步数。如果无法到达终点,则返回 -1

你可以向上、下、左、右四个方向移动,但不能移动到迷宫外,也不能穿过墙壁(即值为 1 的位置)。

输入格式:

  • 第一行包含两个整数 nm,表示迷宫的行数和列数(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步。

提示:

  1. 使用广度优先搜索(BFS)算法可以高效地解决迷宫最短路径问题。
  2. 可以利用队列来存储每一步的状态,并记录当前位置的步数。
  3. 如果在遍历过程中遇到终点 (n-1, m-1),直接输出当前步数。
  4. 注意边界条件的判断以及如何处理无法到达终点的情况。

解题思路:

  1. 初始化一个队列,将起点 (0,0) 和当前步数 1 加入队列。
  2. 在队列不为空时,取出当前节点并检查四个方向的相邻节点是否可以移动:
    • 如果可以移动,且未被访问过,将该节点加入队列,并标记为已访问。
    • 如果到达终点 (n-1, m-1),则输出当前步数。
  3. 如果队列为空且没有找到终点,输出 -1