AcWing 173. 矩阵距离
原题链接
简单
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1e3+10, M = N * N;
int m , n;
int dist[N][N];
typedef pair<int ,int > P;
P q[M];
char s[N][N];
void bfs()
{
int hh = 0, tt = -1;
memset(dist, -1, sizeof dist);
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j++)
{
if(s[i][j] == '1')
{
dist[i][j] = 0;
q[++tt] = {i,j};
}
}
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
while(hh <= tt)
{
auto t = q[hh++];
for(int i = 0; i < 4; i++)
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 0 || b < 0 || a >= n || b >= m) continue;
if(dist[a][b] != -1) continue;
dist[a][b] = dist[t.x][t.y] + 1;
q[++tt] = {a,b};
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
{
scanf("%s",s[i]);
}
bfs();
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
cout << dist[i][j] << ' ';
cout << endl;
}
}