题目描述
给定一个N行M列的01矩阵A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:
$
dist(A[i][j],A[k][l])=|i−k|+|j−l|
$
输出一个N行M列的整数矩阵B,其中:
$
B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}dist(A[i][j],A[x][y])
$
说人话:
就是(i,j)处的值就是曼哈顿距离与之最近的一个1和它的距离。
样例
3 4
0001
0011
0110
算法1
BFS
若某个点的距离为x,其上下左右相邻的点距离为x+1,因此可以采用BFS进行搜索,将相邻的未知区域的距离值置为当前值+1.
时间复杂度
$O(mn)$
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
int n,m;
const int N = 1010;
int B[N][N];
int d[N][N];
int main()
{
scanf("%d%d",&n,&m);
getchar();
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < m ; j++)
B[i][j] = getchar()-'0';
getchar();
}
queue<pair<int,int>> q;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
if(B[i][j])
q.push({i,j});
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,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 && !B[a][b]) {
d[a][b] = d[x][y] + 1;
B[a][b] = 1;
q.push({a,b});
}
}
}
for(int i = 0 ; i < n ; i++) {
for(int j =0 ; j < m ; j++) {
printf("%d ",d[i][j]);
}
puts("");
}
return 0;
}