B3625 迷宫寻路 題解

ShanCreeperPro · 2022-04-23 19:11:11 · 题解

B3625 迷宫寻路 題解

可以使用 dfs 或 bfs 解开。

题目大意： 给定 n\times m 的矩阵，其中 # 表示障碍，问能否只能往上下左右的方向从 (1,1) 走到 (n,m)。

思路1：dfs。

dfs 的实现方法不重要，原理很重要：

向前走，碰壁就回头，换一条路走。

我们使用 dfs 访问 (x,y)，若不是终点，则尝试往四个方向中的一个寻找答案。

那么这个 dfs 就可以这么写：

• 排除非法情况，比如坐标越界和遇到障碍物；
• 如果访问过，则跳过；
• 如果没访问过，继续处理并标记已访问；
• 如果得到答案，退出；
• 否则向四个方向继续扩展。

思路2：bfs。

dfs 的方法就是找一条路走，直到碰壁后换一条走。

还有一种方法，我们可以逐层展开搜索：

• 搜索一步能到达的点；
• 搜索两步能到达的点；
• 搜索三步能到达的点；

这种方法我们成为广度优先搜索（宽度优先搜索，bfs）。

使用广度优先搜索就要使用到队列，存储待访问的点。

所以我们的 bfs 可以这么写：

• 把起始点 (1,1) 入队；
• 如果队列非空：
  • 弹出队首 (x,y)；
  • 判断 (x,y) 是否非法，若非法，跳过；
  • 把 (x,y) 相邻的点入队；

管理员注：

由于课程需要本题不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】