题解 | #迷宫问题#

#include <iostream>
#include <vector>
#include <queue>
#include <array>
using namespace std;

array<int, 4> dx = {-1, 0, 1, 0};
array<int, 4> dy = {0, -1, 0, 1};

bool Bfs(int x, int y, vector<vector<int>>& arr, vector<pair<int, int>>& path) {
    arr[x][y] = -1;
    int n = arr.size();
    int m = arr[0].size();
    if (x == n-1 && y == m-1) {
        path.emplace_back(make_pair(x, y));
        return true;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 ||nx > n-1 || ny < 0 || ny > m-1 || arr[nx][ny] == -1 || arr[nx][ny] == 1)continue;
        
        if(Bfs(nx, ny, arr, path)){
            path.emplace_back(make_pair(x, y));
            return true;
        }
    }
    return false;
}

int main() {
    int n, m;
    queue<pair<int, int>> q;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector(m, 0));
    for (auto& row : arr) {
        for (auto& col : row)
            cin >> col;
    }
    vector<pair<int, int>> path;
    Bfs(0, 0, arr, path);
    for(auto iter = path.rbegin(); iter != path.rend(); iter++){
        printf("(%d,%d)\n", iter->first, iter->second);
    }
}
// 64 位输出请用 printf("%lld")