题解 | #迷宫问题#(输入输出+矩阵+BFS)

解题思路

1.注意矩阵数据的输入,使用queue<vector<pair<int,int>>>存储从起点到当前点的路径,使用广度优先搜索即可;

代码

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

int main(){
    int m, n;
    cin >> m;
    cin >> n;
    vector<vector<int>> mat(m, vector<int>(n));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            int val;
            cin >> val;
            mat[i][j] = val;
        }
    }
    vector<vector<bool>> isVisited(m, vector<bool>(n));
    queue<vector<pair<int, int>>> q; //存储从起点到当前点的路径
    const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    q.push({{0, 0}});
    isVisited[0][0] = true;
    while(!q.empty()){
        auto v = q.front();
        int n1 = v.size();
        q.pop();
        int x0 = v[n1-1].first, y0 = v[n1-1].second;
        if(x0 == m - 1 && y0 == n - 1){
            for(auto& p : v){
                cout << '(' << p.first << ',' << p.second << ')';
                if(p.first != m - 1 || p.second != n - 1) cout << endl; //最后一个位置不需要换行
            }
            break;
        }
        for(int i = 0; i < 4; i++){
            int x1 = x0 + dx[i], y1 = y0 + dy[i];
            if(0 <= x1 && x1 < m && 0 <= y1 && y1 < n && !isVisited[x1][y1] && mat[x1][y1] == 0){
                vector<pair<int, int>> t(v);
                t.push_back({x1, y1});
                q.push(t);
                isVisited[x1][y1] = true;
            }
        }
    }
    return 0;
}