[数据结构与算法]【acwing】173. 矩阵距离（多源bfs)

穿越隧道

和血色先锋队几乎相同，都是多源bfs.
觉得：多源bfs，就是多个起点同时开始广搜，谁先搜到就是最短的路径。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
const int N = 1e3 + 10;
char g[N][N];
int dis[N][N];
pii q[N*N];
//所为多源bfs，就是多个起点同时开始广搜，谁先搜到就是最短的路径。
int n,m;
int main(){
    cin >> n >> m;
    int hh = 0, tt = 0;
    memset(dis,-1,sizeof(dis));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
            if(g[i][j] == '1'){
                dis[i][j] = 0;
                q[tt++] = {i,j};
            }
        }
    }
    int dx[] = {-1,0,1,0};
    int dy[] = {0,1,0,-1};
    while(hh < tt){
        pii t = q[hh++];
        for(int i = 0; i < 4; i++){
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a >= 1 && a <= n && b >= 1 && b <= m && dis[a][b] == -1){
                dis[a][b] = dis[t.x][t.y] + 1;
                q[tt++] ={a,b};
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << dis[i][j] <<" ";
        }
        puts("");
    }
    return 0;
}