题解 | #迷宫问题#

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> maze(N, vector<int>(M));
    vector<vector<pair<int, int>>> parent(N, vector<pair<int, int>>(M, {-1, -1}));
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    vector<pair<int, int>> directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> maze[i][j];
        }
    }

    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;

    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();
        
        int x = current.first;
        int y = current.second;

        if (x == N - 1 && y == M - 1) break;

        for (const auto& dir : directions) {
            int newX = x + dir.first;
            int newY = y + dir.second;

            if (newX >= 0 && newX < N && newY >= 0 && newY < M && !visited[newX][newY] && maze[newX][newY] == 0) {
                q.push({newX, newY});
                visited[newX][newY] = true;
                parent[newX][newY] = {x, y};
            }
        }
    }

    vector<pair<int, int>> path;
    int x = N - 1, y = M - 1;

    while (!(x == 0 && y == 0)) {
        path.emplace_back(x, y);
        pair<int, int> p = parent[x][y];
        x = p.first;
        y = p.second;
    }
    path.emplace_back(0, 0);
    reverse(path.begin(), path.end());

    for (const auto& p : path) {
        cout << "(" << p.first << "," << p.second << ")" << endl;
    }

    return 0;
}

bfs的一种做法