c++迷宫问题求最短路径

对于迷宫问题求最短路径，可以使用广度优先搜索算法（BFS）来解决。

具体实现步骤如下：

1. 定义一个结构体表示迷宫中的一个点，包含该点的行、列和步数。

struct Point {
    int x, y, step;
};

2. 定义一个队列用于存放待搜索的点。

queue<Point> q;

3. 将起点加入队列，并标记为已访问。

q.push(Point{start_x, start_y, 0});
visited[start_x][start_y] = true;

4. 循环搜索队列中的点，直到队列为空或者找到终点。

while (!q.empty()) {
    Point cur = q.front();
    q.pop();

    // 判断是否到达终点
    if (cur.x == end_x && cur.y == end_y) {
        return cur.step;
    }

    // 向四个方向扩展
    for (int i = 0; i < 4; ++i) {
        int next_x = cur.x + dx[i];
        int next_y = cur.y + dy[i];

        // 判断是否越界或者已访问
        if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m || visited[next_x][next_y]) {
            continue;
        }

        // 判断是否可以通过
        if (maze[next_x][next_y] == '.') {
            q.push(Point{next_x, next_y, cur.step + 1});
            visited[next_x][next_y] = true;
        }
    }
}

完整代码：

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 1005;

struct Point {
    int x, y, step;
};

int n, m;
int start_x, start_y, end_x, end_y;
char maze[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int bfs() {
    queue<Point> q;
    q.push(Point{start_x, start_y, 0});
    visited[start_x][start_y] = true;

    while (!q.empty()) {
        Point cur = q.front();
        q.pop();

        // 判断是否到达终点
        if (cur.x == end_x && cur.y == end_y) {
            return cur.step;
        }

        // 向四个方向扩展
        for (int i = 0; i < 4; ++i) {
            int next_x = cur.x + dx[i];
            int next_y = cur.y + dy[i];

            // 判断是否越界或者已访问
            if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m || visited[next_x][next_y]) {
                continue;
            }

            // 判断是否可以通过
            if (maze[next_x][next_y] == '.') {
                q.push(Point{next_x, next_y, cur.step + 1});
                visited[next_x][next_y] = true;
            }
        }
    }

    // 无法到达终点
    return -1;
}

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

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> maze[i][j];
            if (maze[i][j] == 'S') {
                start_x = i;
                start_y = j;
            } else if (maze[i][j] == 'E') {
                end_x = i;
                end_y = j;
            }
        }
    }

    int ans = bfs();
    if (ans == -1) {
        cout << "Can't reach the end point!" << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}