当前位置: 首页 > news >正文

迷宫路径搜索问题:BFS与DFS算法详解

问题描述

这是一个经典的迷宫路径搜索问题。给定一个 n × n 的字符矩阵迷宫,其中 '.' 表示通路,'#' 表示墙壁。同时给出起点坐标 (ha, la) 和终点坐标 (hb, lb)。规则是只能向上、下、左、右四个方向移动,不能走出边界,也不能走到 '#' 上。目标是判断是否能从起点走到终点。

特殊情况:如果起点或终点本身就是墙壁 '#',则直接输出 "NO"。

算法选择

我们可以使用广度优先搜索 (BFS)深度优先搜索 (DFS)来解决。BFS 是解决此类最短路径或连通性问题的标准方法,而 DFS 代码通常更简洁。

C++ 代码实现(BFS版本)

这里使用 BFS(广度优先搜索)实现:

#include <iostream> #include <vector> #include <queue> #include <string> using namespace std; // 定义方向数组:上、下、左、右 int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; // 定义坐标结构体 struct Point { int x, y; }; void solve() { int n; cin >> n; // 存储迷宫地图 vector<string> maze(n); for (int i = 0; i < n; ++i) { cin >> maze[i]; } int ha, la, hb, lb; cin >> ha >> la >> hb >> lb; // 特判:如果起点或终点是墙壁,直接无法到达 if (maze[ha][la] == '#' || maze[hb][lb] == '#') { cout << "NO" << endl; return; } // 记录是否访问过该点,防止重复走 vector<vector<bool>> visited(n, vector<bool>(n, false)); queue<Point> q; // 将起点加入队列并标记为已访问 q.push({ha, la}); visited[ha][la] = true; bool found = false; while (!q.empty()) { Point curr = q.front(); q.pop(); // 如果当前点是终点,说明找到了路径 if (curr.x == hb && curr.y == lb) { found = true; break; } // 尝试向四个方向移动 for (int i = 0; i < 4; ++i) { int nx = curr.x + dx[i]; int ny = curr.y + dy[i]; // 检查边界条件: // 1. 不越界 (0 <= nx < n 且 0 <= ny < n) // 2. 不是墙壁 (maze[nx][ny] != '#') // 3. 没有被访问过 (!visited[nx][ny]) if (nx >= 0 && nx < n && ny >= 0 && ny < n && maze[nx][ny] != '#' && !visited[nx][ny]) { visited[nx][ny] = true; // 标记为已访问 q.push({nx, ny}); // 加入队列 } } } if (found) { cout << "YES" << endl; } else { cout << "NO" << endl; } } int main() { // 优化输入输出效率 ios_base::sync_with_stdio(false); cin.tie(NULL); int k; if (cin >> k) { while (k--) { solve(); } } return 0; }

代码关键点解析

数据结构

  • vector<string> maze:用来存储迷宫地图,string 可以直接通过下标访问字符,非常方便。
  • queue<Point>:BFS 的核心队列,用来存放待探索的坐标。
  • vector<vector<bool>> visited:这是一个二维布尔数组,用来记录哪些格子已经走过了。非常重要,如果不记录,程序会在两个格子之间无限循环导致超时或崩溃。

边界检查

在尝试移动到新坐标 (nx, ny) 时,必须首先检查nx >= 0 && nx < n等条件,防止数组越界访问。

多组数据

题目第一行输入 k,表示有 k 组数据,所以主函数里用了一个while(k--)循环来调用处理逻辑。

DFS版本实现

这题用 BFS 是最稳妥的,其实用 DFS(递归)写起来代码更短:

#include <iostream> #include <vector> #include <string> using namespace std; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; bool dfs(vector<string>& maze, vector<vector<bool>>& visited, int x, int y, int hb, int lb) { if (x == hb && y == lb) return true; visited[x][y] = true; for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < maze.size() && ny >= 0 && ny < maze.size() && maze[nx][ny] != '#' && !visited[nx][ny]) { if (dfs(maze, visited, nx, ny, hb, lb)) { return true; } } } return false; } void solve() { int n; cin >> n; vector<string> maze(n); for (int i = 0; i < n; ++i) { cin >> maze[i]; } int ha, la, hb, lb; cin >> ha >> la >> hb >> lb; if (maze[ha][la] == '#' || maze[hb][lb] == '#') { cout << "NO" << endl; return; } vector<vector<bool>> visited(n, vector<bool>(n, false)); if (dfs(maze, visited, ha, la, hb, lb)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int k; if (cin >> k) { while (k--) { solve(); } } return 0; }

算法对比

特性BFSDFS
代码复杂度中等,需要队列简单,递归实现
空间复杂度O(n²),队列可能存储大量节点O(n²),递归栈深度
适用场景求最短路径判断连通性
本题推荐更稳妥,不易栈溢出代码简洁

总结

迷宫路径搜索是图论中的基础问题,BFS 和 DFS 都是有效的解决方法。BFS 更适合需要最短路径的场景,而 DFS 代码更简洁。在实际解题时,可以根据题目要求和数据规模选择合适的算法。

http://www.jsqmd.com/news/1133138/

相关文章:

  • AMD Ryzen终极调优指南:如何用SDT调试工具解锁隐藏性能
  • 每日 AI 研究简报 · 2026-07-05
  • 工业级 C++ 的生命周期怪圈:深度解密 std::enable_shared_from_this 与 shared_from_this()
  • STM32与STC3115构建高精度电池管理系统设计
  • 在数据分析中,如何通过机器学习方法进行数据建模?
  • 5步掌握AMD Ryzen调试工具:从新手到硬件掌控者
  • CK+ 与 DISFA 数据集实战:从 593 个视频序列到 13 万帧的微表情分析
  • 天学网英语教学产品深度评测:12省市37校实测数据与选型指南
  • Havenlon|AI 时代的执行控制(一):审批通过,不等于执行安全
  • LTC6903与PIC18LF47K40实现高精度数字频率控制
  • 3种方法深度破解Beyond Compare 5授权机制:RSA加密逆向工程完全指南
  • BetterNCM-Installer完整指南:3分钟搞定网易云音乐插件系统
  • Claude Code砍80%提示词:AI降本从拆Prompt债
  • 终极Steam创意工坊下载指南:如何用WorkshopDL免费获取1000+游戏模组
  • MC6470与PIC18F47K40构建6DOF运动控制系统指南
  • WasmEngine实战案例:如何构建高并发、安全隔离的认证服务
  • SLAM 如何一步步迭代到 SE(3)
  • 4-20mA电流环工业应用与STM32L4A6RG硬件设计
  • 基于栅格插值的MIKE URBAN大规模管网快速概化
  • 车企数据安全新范式:四折叠透明加解密方案全解析
  • 如何让老款Mac免费升级到最新macOS:OpenCore Legacy Patcher终极指南
  • 88%的Agent项目死于上线前, “Harness即数据集“才是你真正的护城河
  • 5个核心技巧:掌握西北工业大学LaTeX论文模板的高效写作
  • STM32与MP8859构建智能DC-DC降压电源系统
  • 【系统与实战双精通】VS Code 调试 ROS2 Python 节点与 Launch 系统指南
  • 《秦时明月》系列:中国3D武侠动画的技术演进与艺术价值解析
  • XTR116芯片在4-20mA电流环设计中的关键应用
  • 射阳家电安装服务内容介绍
  • 104-基于51单片机智能远近光灯【Proteus仿真+Keil程序+报告+原理图】
  • 告别枯燥刷本:FGO自动化脚本终极指南