尧图网站建设 尧图网络
  • 首页
  • 关于我们
  • 服务项目
  • 案例展示
  • 建站流程
  • 资讯中心
  • 联系我们
首页/资讯中心/详情

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

迷宫路径搜索问题:BFS与DFS算法详解
📅 发布时间:2026/7/6 6:45:01

问题描述

这是一个经典的迷宫路径搜索问题。给定一个 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 代码更简洁。在实际解题时,可以根据题目要求和数据规模选择合适的算法。

相关新闻

  • 在数据分析中,如何通过机器学习方法进行数据建模?
  • 工业级 C++ 的生命周期怪圈:深度解密 std::enable_shared_from_this 与 shared_from_this()
  • 天学网英语教学产品深度评测:12省市37校实测数据与选型指南

最新新闻

  • Axolotl与LLaMA-Factory微调大模型实战全流程
  • 模型越强,工具调用越差?Anthropic新模型的诡异退化
  • 打通CAN通信壁垒——ZLG与Vector XL无缝桥接解决方案
  • 完成了一二章
  • openEuler agent-skills API参考手册:全面掌握技能调用接口
  • 李宏毅2021机器学习HW1调优:从1.597到1.010的3个关键参数调整

日新闻

  • AI智能体安全防护框架AgentGuard:从原理到实战部署指南
  • KMX63与PIC18F26K40硬件组合及低功耗设计实践
  • 基于YOLO13改进的门体检测模型:C3k2模块与PoolingFormer技术解析

周新闻

  • 基于YOLOv12的番茄成熟度智能检测系统开发
  • 终极RimWorld模组管理指南:用RimSort告别模组冲突烦恼
  • AI Agent框架开发:从理论到实践的完整指南

月新闻

  • 2026年6月公司网站搭建最新热门渠道测评:四大低成本/零代码平台对比+避坑
  • 【Linux】Linux arm 编译QT程序,出现expected “}“报错
  • 【MATLAB例程】四基站二维AOA定位与距离辅助增强对比仿真。基于角度观测和测距修正的固定目标平面定位精度分析

关于尧图

  • 公司简介
  • 团队介绍
  • 企业文化
  • 荣誉资质

服务项目

  • 定制开发
  • 电商建站
  • UI 设计
  • 运维服务

快速链接

  • 案例展示
  • 建站流程
  • 常见问题
  • 资讯中心

联系方式

  • 📍北京市朝阳区互联网产业园 A 座 10 层
  • 📞400-888-8888
  • ✉️contact@rkmt.cn
  • 🕐周一至周日 9:00-21:00

© 2024 北京尧图网络科技有限公司 版权所有 | 京 ICP 备 XXXXXXXX 号