SWUST OJ 668 迷宫路径搜索DFS与BFS算法实战解析与性能对比迷宫路径搜索是算法竞赛中的经典问题类型也是检验编程者基础算法掌握程度的试金石。在SWUST OJ第668题小偷跑了中我们需要为一个5×5的迷宫矩阵找到从起点(0,0)到终点(4,4)的可行路径。本文将深入剖析深度优先搜索(DFS)和广度优先搜索(BFS)两种算法的实现差异并通过实际代码对比它们的性能表现。1. 迷宫问题与算法选择基础迷宫路径搜索问题本质上是一个图论中的路径查找问题其中每个网格单元可以看作图中的一个节点相邻的可通行单元之间则存在边连接。对于5×5的网格迷宫我们需要考虑以下几个关键约束条件移动限制只能上下左右移动不能斜向移动即曼哈顿距离移动障碍表示矩阵中1表示障碍物0表示可通行路径路径唯一性题目保证最多只有一条有效路径在解决这类问题时DFS和BFS是两种最基础的搜索策略DFS沿着一条路径深入探索直到无法继续再回溯尝试其他分支BFS逐层扩展搜索先探索距离起点最近的节点提示虽然DFS和BFS都能找到路径但BFS找到的必定是最短路径而DFS找到的路径则取决于搜索顺序和实现方式。2. DFS算法实现与优化技巧深度优先搜索采用递归或栈的方式实现其核心思想是一条路走到黑。下面是针对SWUST OJ 668题的DFS实现代码#include stdio.h #include stdbool.h #define SIZE 5 int maze[SIZE][SIZE]; bool visited[SIZE][SIZE]; int path[SIZE*SIZE][2]; int pathLength 0; bool found false; // 移动方向右、下、左、上 int directions[4][2] {{0,1}, {1,0}, {0,-1}, {-1,0}}; void printPath() { for(int i0; ipathLength; i) { printf((%d,%d) , path[i][0], path[i][1]); } printf(\n); } void dfs(int x, int y) { // 到达终点 if(x SIZE-1 y SIZE-1) { path[pathLength][0] x; path[pathLength][1] y; pathLength; printPath(); found true; return; } // 标记当前节点为已访问 visited[x][y] true; path[pathLength][0] x; path[pathLength][1] y; pathLength; // 尝试四个方向 for(int i0; i4; i) { int nx x directions[i][0]; int ny y directions[i][1]; // 检查新位置是否有效 if(nx0 nxSIZE ny0 nySIZE !visited[nx][ny] maze[nx][ny]0) { dfs(nx, ny); if(found) return; // 找到路径后立即返回 } } // 回溯 pathLength--; visited[x][y] false; } int main() { // 读取迷宫输入 for(int i0; iSIZE; i) { for(int j0; jSIZE; j) { scanf(%d, maze[i][j]); } } // 初始化访问数组 for(int i0; iSIZE; i) { for(int j0; jSIZE; j) { visited[i][j] false; } } // 从起点开始搜索 dfs(0, 0); if(!found) { printf(No Way!\n); } return 0; }这段代码实现了DFS的核心逻辑并包含了几处优化提前终止找到路径后立即返回避免不必要的搜索路径记录使用数组保存当前路径而非每次递归都重新构建方向数组统一处理四个方向的移动使代码更简洁DFS的时间复杂度在最坏情况下为O(4^(n^2))其中n为迷宫边长。对于5×5的迷宫这个复杂度是可以接受的。3. BFS算法实现与路径重建广度优先搜索采用队列实现天然适合寻找最短路径。下面是BFS的实现代码#include stdio.h #include stdbool.h #include stdlib.h #define SIZE 5 typedef struct { int x, y; int prev; // 前驱节点在队列中的索引 } Node; int maze[SIZE][SIZE]; bool visited[SIZE][SIZE]; Node queue[SIZE*SIZE]; int front 0, rear 0; // 移动方向右、下、左、上 int directions[4][2] {{0,1}, {1,0}, {0,-1}, {-1,0}}; void printPath(int index) { if(index -1) return; printPath(queue[index].prev); printf((%d,%d) , queue[index].x, queue[index].y); } void bfs() { // 起点入队 queue[rear].x 0; queue[rear].y 0; queue[rear].prev -1; rear; visited[0][0] true; while(front rear) { Node current queue[front]; // 检查是否到达终点 if(current.x SIZE-1 current.y SIZE-1) { printPath(front); printf(\n); return; } // 探索四个方向 for(int i0; i4; i) { int nx current.x directions[i][0]; int ny current.y directions[i][1]; // 检查新位置是否有效 if(nx0 nxSIZE ny0 nySIZE !visited[nx][ny] maze[nx][ny]0) { visited[nx][ny] true; queue[rear].x nx; queue[rear].y ny; queue[rear].prev front; rear; } } front; } // 没有找到路径 printf(No Way!\n); } int main() { // 读取迷宫输入 for(int i0; iSIZE; i) { for(int j0; jSIZE; j) { scanf(%d, maze[i][j]); } } // 初始化访问数组 for(int i0; iSIZE; i) { for(int j0; jSIZE; j) { visited[i][j] false; } } // 执行BFS搜索 bfs(); return 0; }BFS实现的关键点包括队列结构使用队列存储待探索的节点前驱记录每个节点记录其前驱节点便于重建路径层级扩展确保先探索距离起点更近的节点BFS的时间复杂度为O(n^2)其中n为迷宫边长因为它最多访问每个节点一次。4. 算法性能对比与适用场景为了直观比较DFS和BFS在迷宫问题中的表现我们设计以下测试案例测试迷宫1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 测试迷宫2 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0两种算法的性能对比如下表所示指标DFSBFS路径查找方式深度优先广度优先找到的路径性质取决于实现不一定最短保证是最短路径空间复杂度O(n)递归栈O(n^2)队列最坏时间复杂度O(4^(n^2))O(n^2)适用场景路径存在性检查最短路径查找实现难度较简单需处理路径重建在实际OJ测试中我们发现简单迷宫两种算法都能快速找到解但BFS的路径更优复杂迷宫DFS可能陷入深层递归而BFS表现更稳定无解情况BFS能更快确定无解因为它会系统性地探索所有可能注意虽然DFS的递归实现简洁但对于大型迷宫可能导致栈溢出。在实际应用中可以考虑使用显式栈的迭代实现。5. 算法竞赛中的优化技巧在算法竞赛中针对迷宫类问题还有以下实用技巧方向数组预处理// 四个方向右、下、左、上 int dirs[4][2] {{0,1}, {1,0}, {0,-1}, {-1,0}}; // 八个方向如果允许斜向移动 int dirs8[8][2] {{0,1},{1,1},{1,0},{1,-1}, {0,-1},{-1,-1},{-1,0},{-1,1}};边界检查宏定义#define isValid(x, y) ((x)0 (x)SIZE (y)0 (y)SIZE)状态压缩对于大型迷宫可以使用位运算压缩访问状态双向BFS当起点和终点都已知时可以同时从两端开始搜索显著提高效率启发式搜索结合估价函数的A*算法可以进一步优化搜索效率在SWUST OJ这类编程竞赛中理解DFS和BFS的核心思想比记忆代码模板更重要。实际解题时应根据题目特点选择合适的算法并考虑可能的优化空间。