小马智行 Acwing 173. 矩阵距离

小马智行 Acwing 173. 矩阵距离

思路：

多源点最短路问题，我们可以使用DIjkstra或者BFS进行搜索。

代码：

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
typedef pair<int,int> PII;
const int N = 1010,M = N * N;
char S[N][N];
int d[N][N];
int n,m;

int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};

int main(){
    cin>>n>>m;
    for(int i = 0;i < n;i ++)
        for(int j = 0; j < m; j++)
            cin>>S[i][j];
    
    queue<PII> q;
    memset(d,-1,sizeof d);
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(S[i][j] == '1'){
                q.push({i,j});
                d[i][j] = 0;
            }
        }
    }
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        int x = t.first, y = t.second;
        
        for(int i = 0; i < 4; i++){
            int a = x + dx[i],b = y + dy[i];
            if(a >= 0 && a < n && b >= 0 && b < m && S[a][b] == '0' && d[a][b] == -1){
                q.push({a,b});
                d[a][b] = d[x][y] + 1;
            }
        }
    }
    
    for(int i = 0;i < n; i++){
            for(int j = 0; j < m; j++)
                cout<<d[i][j]<<' ';
            puts("");
        }
    return 0;
}