自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:00，当前版本为作者最后更新于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)$ 相邻的点入队；

管理员注：

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

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