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()