C++解决走迷宫问题：DFS、BFS算法应用

---

例如下面的迷宫：

// 迷宫的表示：0表示可以走，1表示障碍
vector<vector<int>> maze = {{0, 0, 1, 0, 0},{1, 0, 1, 1, 0},{1, 0, 0, 1, 0},{0, 0, 0, 0, 0},{1, 1, 1, 1, 0}
};

要实现解决迷宫的问题，可以使用回溯法深度优先搜索(DFS）或者广度优先搜索（BFS）。

思路：

迷宫中的 0 表示可走的路，1 表示障碍。
起点是 (0, 0)，终点是 (n-1, m-1)。
可以向上、下、左、右四个方向移动。
通过回溯法探索每个可能的路径，当找到终点时，返回路径。

下面分别使用DFS和BFS来实现。

DFS

/*深度搜索  dfs*/#include <iostream>
#include <vector>using namespace std;// 定义行的上下左右四个方向的移动
// -1表示向上移动，1表示向下移动，0表示不改变行
int row_dir[] = { -1, 1, 0, 0 };  // 定义行的上下左右四个方向的移动
// -1表示向左移动，1表示向右移动，0表示不改变列
int col_dir[] = { 0, 0, -1, 1 };// 检查当前位置是否有效，且未被访问过
bool isValid(int x, int y, const vector<vector<int>>& maze, vector<vector<bool>>& visited) 
{return (x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() &&maze[x][y] == 0 && !visited[x][y]);
}// 回溯法解决迷宫问题
bool solveMaze(int x, int y, const vector<vector<int>>& maze, vector<vector<bool>>& visited, vector<pair<int, int>>& path) 
{// 到达终点if (x == maze.size()