迷宫出口c++dfs

以下是使用C++的DFS算法来找到迷宫的出口的示例代码：

#include <iostream>
#include <vector>

using namespace std;

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

// 定义迷宫的起点和终点
const int start_x = 0;
const int start_y = 0;
const int end_x = 4;
const int end_y = 4;

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

// 定义访问标记数组
vector<vector<bool>> visited(N, vector<bool>(M, false));

// 定义方向数组，用于控制上下左右四个方向的移动
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// DFS函数，用于搜索迷宫的出口
bool dfs(int x, int y) {
    // 如果当前位置是终点，则返回true
    if (x == end_x && y == end_y) {
        return true;
    }
    
    // 标记当前位置已访问
    visited[x][y] = true;
    
    // 尝试四个方向的移动
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 判断新位置是否合法，并且没有被访问过，并且不是障碍物
        if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny] && maze[nx][ny] == 0) {
            // 递归搜索新位置
            if (dfs(nx, ny)) {
                return true;
            }
        }
    }
    
    // 如果四个方向都无法到达终点，则返回false
    return false;
}

int main() {
    // 调用DFS函数，从起点开始搜索
    if (dfs(start_x, start_y)) {
        cout << "exist!" << endl;
    } else {
        cout << "not exist!" << endl;
    }
    
    return 0;
}