在c++中使用递归回溯迷宫

#include <iostream>
#include <vector>

using namespace std;

// 定义迷宫的大小
const int N = 5;
const int M = 5;

// 定义迷宫的地图
vector<vector<int>> maze = {
    {1, 1, 1, 1, 1},
    {1, 0, 0, 0, 1},
    {1, 1, 1, 0, 1},
    {1, 0, 0, 0, 1},
    {1, 1, 1, 1, 1}
};

// 定义标记数组，用于记录路径
vector<vector<int>> visited(N, vector<int>(M, 0));

// 定义方向数组，用于控制移动方向
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

// 判断当前位置是否合法
bool isValid(int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= M) {
        return false;
    }
    if (maze[x][y] == 1 || visited[x][y] == 1) {
        return false;
    }
    return true;
}

// 递归回溯函数
bool solveMaze(int x, int y) {
    // 到达终点
    if (x == N - 1 && y == M - 1) {
        visited[x][y] = 1;
        return true;
    }

    // 标记当前位置已访问
    visited[x][y] = 1;

    // 尝试四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(nx, ny)) {
            if (solveMaze(nx, ny)) {
                return true;
            }
        }
    }

    // 回溯，取消当前位置的标记
    visited[x][y] = 0;
    return false;
}

int main() {
    if (solveMaze(0, 0)) {
        cout << "迷宫有解！" << endl;
    } else {
        cout << "迷宫无解！" << endl;
    }
    return 0;
}