c++迷宫问题

迷宫问题是一个经典的算法问题，通常使用深度优先搜索或广度优先搜索进行解决。以下是一个使用深度优先搜索算法的c++实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100;
int n, m;
char maze[MAXN][MAXN];  // 迷宫地图
bool vis[MAXN][MAXN];   // 标记是否访问过

// 方向数组，依次为上、右、下、左
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// 深度优先搜索
bool dfs(int x, int y) {
    // 到达终点
    if (maze[x][y] == 'G') {
        return true;
    }

    // 标记为已访问
    vis[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 && maze[nx][ny] != '#' && !vis[nx][ny]) {
            if (dfs(nx, ny)) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    cin >> n >> m;

    // 读入迷宫地图
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }

    // 从起点开始搜索
    int sx, sy;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }

    if (dfs(sx, sy)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

这个算法的时间复杂度为 $O(nm)$，其中 $n$ 和 $m$ 分别为迷宫的行数和列数。