题目描述
给定一个N行M列的01矩阵A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：
dist(A[i][j],A[k][l])=|i−k|+|j−l|
dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个N行M列的整数矩阵B，其中：
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
输入格式
第一行两个整数n,m。
接下来一个N行M列的01矩阵，数字之间没有空格。
输出格式
一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。
数据范围
1≤N,M≤1000
样例
输入样例：
3 4
0001
0011
0110
输出样例：
3 2 1 0
2 1 0 0
1 0 0 1
算法1 宽搜
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！暴力出奇迹！
暴力出奇迹！
暴力出奇迹！暴力出奇迹！暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
C++ 代码
include[HTML_REMOVED]
using namespace std;
int n,m,d[1005][1005];
char a[1005][1005];
int dx[5]={-1,1,0,0};
int dy[5]={0,0,-1,1};
queue[HTML_REMOVED] > q;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i)
{
cin>>a[i]+1;
}
memset(d,-1,sizeof(d));
for(int i=1;i<=n;i)
{
for(int j=1;j<=m;j)
{
if(a[i][j]==‘1’)
{
q.push(make_pair(i,j));
d[i][j]=0;
}
}
}
while(q.size()!=0)
{
pair[HTML_REMOVED] sum=q.front();
q.pop();
for(int k=0;k<4;k)
{
pair[HTML_REMOVED] next(sum.first+dx[k],sum.second+dy[k]);
if(next.first<1||next.second<1||next.first>n||next.second>m) continue;
if(d[next.first][next.second]==-1)
{
d[next.first][next.second]=d[sum.first][sum.second]+1;
q.push(next);
}
}
}
for(int i=1;i<=n;i)
{
for(int j=1;j<m;j)
{
cout<<d[i][j]<<” “;
}
cout<<d[i][m]<<endl;
}
return 0;
}
