描述
给定一个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])}
即求与每个位置曼哈顿距离最近的1
N,M≤1000。
输入格式
第一行两个整数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 思路：直接对每个1的起点bfs，搜过的点就不用搜了，每个第一次遍历的点，就是其中一个起点到其的最小曼哈顿距离
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
vector<P>v;
int r,c;
char maps[][];
int vis[][];
int way[][] = {,,-,,,,,-};
struct Node
{
int x,y;
};
int num;
void init()
{
scanf("%d%d",&r,&c);
char s[];
for(int i=;i<=r;i++)
{
scanf("%s",s);
for(int j=;j<=c;j++)
{
maps[i][j] = s[j-];
if(maps[i][j] == '')
{
num++;
v.push_back(P(i,j));
vis[i][j] = ;
}
}
}
} void bfs()
{
queue<P>que;
while(!que.empty())que.pop();
for(int i=;i<v.size();i++)que.push(v[i]);
while(!que.empty())
{
P tmp = que.front();
que.pop();
for(int i=;i<;i++)
{
int xx = tmp.first + way[i][];
int yy = tmp.second + way[i][];
if(xx >= && xx <= r && yy >= && yy <= c && !vis[xx][yy])
{
num++;
vis[xx][yy] = vis[tmp.first][tmp.second] + ;
que.push(P(xx,yy));
}
}
if(num == r * c)return;
}
} void print()
{
for(int i=;i<=r;i++)
{
for(int j=;j<=c;j++)
{
printf(j==c?"%d\n":"%d ",vis[i][j]-);
}
}
}
int main()
{
init();
bfs();
print();
}