AcWing 173. 矩阵距离
原题链接
简单
作者:
十六
,
2021-01-14 16:05:55
,
所有人可见
,
阅读 378
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 1e3+10;
typedef pair<int, int> PII;
int n, m;
char g[MAX][MAX];
int dis[MAX][MAX];
int d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
queue<PII> q;
void bfs(){
memset(dis, -1, sizeof dis);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(g[i][j]=='1') dis[i][j] = 0, q.push({i, j});
}
}
while(q.size()){
PII t = q.front();
q.pop();
for(int i=0; i<4; i++){
int x = t.first+d[i][0], y = t.second+d[i][1];
if(x<0 || x>=n || y<0 || y>=m) continue;
if(dis[x][y]!=-1) continue;
dis[x][y] = dis[t.first][t.second] + 1;
q.push({x, y});
}
}
return ;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++) scanf("%s", g[i]);
bfs();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
printf("%d ", dis[i][j]);
}
printf("\n");
}
return 0;
}