c++迷宫问题回溯法

以下是C++中使用回溯法解决迷宫问题的示例代码：

#include <iostream>
using namespace std;

const int MAX = 100; // 迷宫的最大大小
int maze[MAX][MAX]; // 迷宫数组
int m, n; // 迷宫的大小
int startx, starty; // 起点坐标
int endx, endy; // 终点坐标
bool visited[MAX][MAX]; // 标记数组，标记某个位置是否已经访问过

// 定义8个方向的移动
int dx[8] = {0, 1, 1, 1, 0, 0, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, 1, 0, -1};

// 判断某个位置是否可以走
bool is_valid(int x, int y) {
    if (x < 0 || x >= m || y < 0 || y >= n) {
        return false; // 超出边界
    }
    if (maze[x][y] == 1 || visited[x][y]) {
        return false; // 障碍物或已经访问过
    }
    return true;
}

// 回溯函数
bool dfs(int x, int y) {
    visited[x][y] = true; // 标记为已访问
    if (x == endx && y == endy) {
        return true; // 到达终点
    }
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (is_valid(nx, ny)) {
            if (dfs(nx, ny)) {
                return true; // 找到一条路径就返回
            }
        }
    }
    return false; // 没有找到路径
}

int main() {
    // 读入迷宫
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maze[i][j];
        }
    }
    // 读入起点和终点
    cin >> startx >> starty >> endx >> endy;
    // 搜索路径
    if (dfs(startx, starty)) {
        cout << "找到一条路径" << endl;
    } else {
        cout << "没有找到路径" << endl;
    }
    return 0;
}