题解 | 迷宫问题

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int fx[4] = {0,0,1,-1},fy[4] = {1,-1,0,0};
void solve(){
    ll n,m;
    cin >> n >> m;
    vector<vector<int>>mp(n,vector<int>(m,0));
    vector<vector<pair<int,int>>>lu(n,vector<pair<int,int>>(m));
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            cin >> mp[i][j];
        }
    }
    vector<vector<bool>>st(n,vector<bool>(m,0));
    auto bfs = [&](){
        st[0][0] = 1;
        queue<pair<int,int>>q;
        q.push({0,0});
        while(q.size()){
            auto t = q.front();
            q.pop();
            for(int i = 0 ; i < 4 ; i++){
                int tx = t.first + fx[i],ty = t.second + fy[i];
                if(tx < n && tx >= 0 && ty < m && ty >= 0 && !mp[tx][ty] && !st[tx][ty]){
                    q.push({tx,ty});
                    st[tx][ty] = 1;
                    lu[tx][ty] = {t.first,t.second};
                }
            }
        }
    };
    bfs();
    // for(int i = 0 ; i < n ; i++){
    //     for(int j = 0 ; j < m ; j++){
    //         cout << mp[i][j] << ' ';
    //     }cout << '\n';
    // }
    // cout << '\n';
    // for(int i = 0 ; i < n ; i++){
    //     for(int j = 0 ; j < m ; j++){
    //         cout << "(" << lu[i][j].first << ',' << lu[i][j].second << ") ";
    //     }cout << '\n';
    // }
    int x = n - 1,y = m - 1;
    vector<pair<int,int>>ans;
    while(x || y){
        ans.push_back({lu[x][y].first,lu[x][y].second});
        int tx = lu[x][y].first,ty = lu[x][y].second;
        x = tx,y = ty;
    }
    for(int i = ans.size() - 1 ; i >= 0 ; i--){
        cout << "(" << ans[i].first << ',' << ans[i].second << ")" << '\n';
    }
    cout << "(" << n - 1 << "," << m - 1 << ")";
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

呃呃，水题，bfs直接搜索，然后开一个数组记录路径，最后遍历输出就行了，记得把结尾加上