前言
BFS广度优先搜索和DFS深度优先搜索解决迷宫问题
迷宫问题
原题目：迷宫由n行m列的单元格组成(n,m都小于等于50)，每个单元格要吗是空地要吗是障碍物。现在请你找到一条从起点到终点的最短路径长度。
分析
BFS广度优先搜索
首先我们将起点入队，
然后队首节点可拓展的点入队，如果没有可拓展的点，将队首节点出队。重复该步骤直到达到目标位置或者队列为空。
DFS 深度优先搜索
代码如下：
BFS代码
#include <bits/stdc++.h>
using namespace std;const int MAX = 100; // 定义最大矩阵大小
int a[MAX][MAX], v[MAX][MAX]; // a 用于存储迷宫地图，v 用于记录访问状态// 定义点结构体
struct point {int x; // 点的 x 坐标int y; // 点的 y 坐标int step; // 从起点到达该点的步数
};queue<point> r; // 申请队列，用于 BFS 遍历
int dx[4] = {0, 1, 0, -1}; // 四个方向的 x 偏移量（右、下、左、上）
int dy[4] = {1, 0, -1, 0}; // 四个方向的 y 偏移量（右、下、左、上）
/*
5 4
1 1 0 1
1 1 1 1
1 1 0 1
1 0 1 1
1 1 1 0
1 1 4 3
*/
int main() {int n, m; // 迷宫的行数和列数int startx, starty; // 起点的坐标int endx, endy; // 终点的坐标// 读取迷宫的行数和列数cin >> n >> m;// 初始化 v 数组，所有点的访问状态都设为 0（未访问）for(int i = 0; i < MAX; i++) {for(int j = 0; j < MAX; j++) {v[i][j] = 0;}}// 读取迷宫地图for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {cin >> a[i][j];}}// 读取起点和终点的坐标cin >> startx >> starty >> endx >> endy;// 初始化 BFS 的起点point start;start.x = startx;start.y = starty;start.step = 0; // 起点的步数为 0r.push(start); // 将起点入队v[startx][starty] = 1; // 标记起点为已访问int flag = 0; // 标记是否找到路径// 开始 BFS 遍历while(!r.empty()) {int x = r.front().x; // 当前点的 x 坐标int y = r.front().y; // 当前点的 y 坐标int step = r.front().step; // 当前点的步数r.pop(); // 取出队首元素// 如果当前点是终点，输出步数并终止if(x == endx && y == endy) {flag = 1;cout << step << endl;break;}// 遍历四个方向for(int k = 0; k < 4; k++) {int tx = x + dx[k]; // 计算新点的 x 坐标int ty = y + dy[k]; // 计算新点的 y 坐标// 确保新点在合法范围内if(tx >= 1 && tx <= n && ty >= 1 && ty <= m) {// 如果新点是可通行的且未访问过if(a[tx][ty] == 1 && v[tx][ty] == 0) {// 更新新点的坐标和步数point temp;temp.x = tx;temp.y = ty;temp.step = step + 1;r.push(temp); // 将新点入队v[tx][ty] = 1; // 标记新点为已访问}}}}// 如果没有找到路径，输出提示信息if(flag == 0) {cout << "没有路径" << endl;}return 0;
}
DFS代码
#include<bits/stdc++.h>
using namespace std;int endx, endy; // 终点的坐标
int a[100][100]; // 定义地图，1表示空地，0表示障碍物
int v[100][100]; // 访问标记数组，0表示未访问，1表示已访问
int minSteps = 99999999; // 初始化最小步数为一个较大的值，用于存储到达终点的最小步数// 深度优先搜索 (DFS) 函数，x和y表示当前坐标，step表示当前走的步数
void dfs(int x, int y, int step) {// 如果当前坐标是终点if(x == endx && y == endy) {// 如果当前步数小于已知的最小步数，则更新最小步数if(step < minSteps) {minSteps = step;}return; // 返回，继续尝试其他路径}// 顺时针依次试探四个方向（右、下、左、上）// 右移动（坐标[x, y+1]），需要确保不越界且是空地且未访问过if(y + 1 <= 99 && a[x][y + 1] == 1 && v[x][y + 1] == 0) {v[x][y + 1] = 1; // 标记该点为已访问dfs(x, y + 1, step + 1); // 递归调用DFS，步数+1v[x][y + 1] = 0; // 回溯，将该点标记为未访问，以便尝试其他路径}// 下移动（坐标[x+1, y]），需要确保不越界且是空地且未访问过if(x + 1 <= 99 && a[x + 1][y] == 1 && v[x + 1][y] == 0) {v[x + 1][y] = 1; // 标记该点为已访问dfs(x + 1, y, step + 1); // 递归调用DFS，步数+1v[x + 1][y] = 0; // 回溯，将该点标记为未访问}// 左移动（坐标[x, y-1]），需要确保不越界且是空地且未访问过if(y - 1 >= 1 && a[x][y - 1] == 1 && v[x][y - 1] == 0) {v[x][y - 1] = 1; // 标记该点为已访问dfs(x, y - 1, step + 1); // 递归调用DFS，步数+1v[x][y - 1] = 0; // 回溯，将该点标记为未访问}// 上移动（坐标[x-1, y]），需要确保不越界且是空地且未访问过if(x - 1 >= 1 && a[x - 1][y] == 1 && v[x - 1][y] == 0) {v[x - 1][y] = 1; // 标记该点为已访问dfs(x - 1, y, step + 1); // 递归调用DFS，步数+1v[x - 1][y] = 0; // 回溯，将该点标记为未访问}return; // 返回，继续试探其他路径
} int main() {int startx, starty, m, n; // 起点坐标startx, starty，m表示行数，n表示列数cin >> m >> n; // 输入地图的大小，m行n列// 输入地图信息，1表示空地，0表示障碍物for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {cin >> a[i][j]; // 输入每个位置的地形，1为空地，0为障碍} }// 输入起点坐标和终点坐标cin >> startx >> starty >> endx >> endy;// 初始化起点，将起点标记为已访问v[startx][starty] = 1;// 调用DFS从起点开始搜索，初始步数为0dfs(startx, starty, 0);// 如果最终没有找到到达终点的路径，输出-1if(minSteps == 99999999) {cout << -1 << endl; // 无法到达终点} else {// 输出最小步数cout << minSteps << endl;}return 0;
}
BFS和DFS的区别
广度优先搜索：
将队首结点可以拓展的点入队，如果没有可以拓展的点，将队首结点出队。重复上述步骤，直到到达目标位置或者队列为空。BFS搜索到的结果一定是最短的。BFS运用到了队列。
深度优先搜索：
(从某点出发，沿着一个方向往下试探，当找到目标位置，还需回溯，以便找到所有的路径，再比较最短的路径，比较盲目，效率没有BFS高。DFS运用到了栈。