用C++代码递归思想求解迷宫问题代码

在C++中，我们可以使用递归的思想来解决迷宫问题，特别是广度优先搜索(BFS)或深度优先搜索(DFS)算法。这里给出一个基于DFS的简单示例，假设我们有一个二维数组表示迷宫，其中0表示通路，1表示墙壁：

#include <vector>
using namespace std;

// 假设maze[i][j]为迷宫地图，visited用于记录已访问过的节点
bool isMazeValid(vector<vector<int>>& maze, int i, int j) {
    return (i >= 0 && i < maze.size() && j >= 0 && j < maze[0].size() && !maze[i][j]);
}

// 检查是否到达目标位置并返回true
bool reachedTarget(int i, int j, vector<vector<int>>& maze) {
    return i == targetI && j == targetJ;
}

// 递归函数，从起点开始尝试走每一步
void dfs(vector<vector<int>>& maze, int i, int j, vector<vector<bool>>& visited, int& steps) {
    if (reachedTarget(i, j, maze)) {
        cout << "找到了路径，步数：" << steps << endl;
        return;
    }

    visited[i][j] = true;
    steps++;

    // 对邻居进行递归检查
    const int dx[] = {0, 0, -1, 1};
    const int dy[] = {-1, 1, 0, 0};

    for (int k = 0; k < 4; ++k) {
        int ni = i + dx[k], nj = j + dy[k];
        if (isMazeValid(maze, ni, nj) && !visited[ni][nj]) {
            dfs(maze, ni, nj, visited, steps);
        }
    }
}

// 调用函数，起点设为startI, startJ
void solveMaze(vector<vector<int>>& maze, int startI, int startJ) {
    vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size(), false));
    dfs(maze, startI, startJ, visited, 0);
}

在这个例子中，`solveMaze`函数接受迷宫、起点坐标作为输入，然后初始化一个访问矩阵，并通过`dfs`函数进行递归搜索。如果找到终点，就结束递归并输出步数。