题面
给定一个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]=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.因为要到1的距离最小，所以从1开始搜遍附近（+1）然后从这个点继续遍历（+1），因此想到bfs，队列的作用就能实现这个 2.所以先把1的点放入队列，接着就开始bfs改变vis数组
代码：
#include <bits/stdc++.h>
using namespace std
;
typedef pair
<int,int> pa
;
const int maxn
=1004;
int vis
[maxn
][maxn
];
int maze
[maxn
][maxn
];
int dx
[4]={-1,0,1,0};
int dy
[4]={0,1,0,-1};
int n
,m
;
void bfs()
{
queue
<pa
> qu
;
for(int i
=0;i
<n
;i
++)
{
for(int j
=0;j
<m
;j
++)
{
if(maze
[i
][j
]==1)
{
qu
.push({i
,j
});
vis
[i
][j
]=0;
}
}
}
while(!qu
.empty())
{
pa p
=qu
.front();
qu
.pop();
for(int i
=0;i
<4;i
++)
{
int xx
=p
.first
+dx
[i
];
int yy
=p
.second
+dy
[i
];
if(xx
>=0&&xx
<n
&&yy
>=0&&yy
>m
&&vis
[xx
][yy
]==-1)
{
vis
[xx
][yy
]=vis
[p
.first
][p
.second
]+1;
qu
.push({xx
,yy
});
}
}
}
}
int main()
{
cin
>>n
>>m
;
for(int i
=0;i
<n
;i
++)
{
string hh
;
cin
>>hh
;
for(int j
=0;j
<m
;j
++)
{
maze
[i
][j
]=hh
[j
]-'0';
}
}
memset(vis
,-1,sizeof(vis
));
bfs();
for(int i
=0;i
<n
;i
++)
{
for(int j
=0;j
<m
;j
++)
{
cout
<<vis
[i
][j
]<<" ";
}
cout
<<endl
;
}
}
