给定一个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])}
输入格式
第一行两个整数n,m。
接下来一个N行M列的01矩阵，数字之间没有空格。
输出格式
一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。
3 4
0001
0011
0110
输出样例：
3 2 1 0
2 1 0 0
1 0 0 1
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<
int,
int>
PII;
int dx[
4]={-
1,
0,
1,
0},dy[
4]={
0,
1,
0,-
1};
const int N=
1010;
char g[N][N];
int d[N][N],n,m;
queue<PII>
q;
void bfs(){
memset(d,-
1,
sizeof(d));
for(
int i=
0;i<n;i++
)
for(
int j=
0;j<m;j++
){
if(g[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&&d[a][b]==-
1){
d[a][b]=d[x][y]+
1;
q.push({a,b});
}
}
}
}
int main(
void){
cin>>n>>
m;
for(
int i=
0;i<n;i++)cin>>
g[i];
bfs();
for(
int i=
0;i<n;i++
){
for(
int j=
0;j<m;j++
){
if(j!=m-
1)
cout<<d[i][j]<<
' ';
else
cout<<
d[i][j];
}
cout<<
endl;
}
return 0;
}
转载于:https://www.cnblogs.com/programyang/p/11207109.html
