Description
现在我们给出一个n*m的黑白位图，n为行数，m为列数，且该位图中至少含有一个白色的像素。我们用(i,j)来表示第i行第j列的像素，并且定义两像素点p1=(i1,j1)和p2=(i2,j2)之间的距离为：d(p1,p2)=|i1-i2|+|j1-j2|。
对于任意给定的位图，计算出位图中每个像素到与它最近的白色像素之间的距离。
Input
本题有多组输入数据，每组数据第一行包含两个整数n,m，用空格分开，1<=n,m<=182。之后的n行每行包含一个长度为m的由0和1组成的字符串，即第i行第j个字符如果为”1”，那么表示像素(i,j)为白的，否则为黑的。
Output
对于每组数据，输出包含n行，第i行的第j个数字为f(i,j)，表示像素(i,j)到最近的白色像素的距离。每行内的数字用空格分开。
Sample Input 3 4 0001 0011 0110
Sample Output 3 2 1 0 2 1 0 0 1 0 0 1
bfs题，先将为1的点都进队，然后一层一层扩展，只需将矩阵遍历一遍就行
#include"iostream" #include"string.h" #include"stdlib.h" #include"cstdio" #include<queue> using namespace std; int m,n,num; char ai[200][200]; int dis[200][200]; bool sign[200][200]; int fx[4][2]={1,0,-1,0,0,1,0,-1}; struct node { int x,y,step; }bi[40000]; bool check(int a,int b) { if(a>=0&&a<m&&b>=0&&b<n&&!sign[a][b]&&ai[a][b]=='0') return true; return false; } void bfs() { queue<node> jj; node mm,nn; for(int i=0;i<num;i++) jj.push(bi[i]); while(!jj.empty()) { nn=jj.front(); jj.pop(); for(int i=0;i<4;i++) { mm=nn; mm.x+=fx[i][0]; mm.y+=fx[i][1]; if(check(mm.x,mm.y)) { mm.step++; dis[mm.x][mm.y]=mm.step; sign[mm.x][mm.y]=true; jj.push(mm); } } } } int main() { while(cin>>m>>n) { num=0; memset(sign,0,sizeof(sign)); for(int i=0;i<m;i++) scanf("%s",ai[i]); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(ai[i][j]=='1') { dis[i][j]=0; sign[i][j]=true; bi[num].x=i; bi[num].y=j; bi[num].step=0; num++; } } } bfs(); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { cout<<dis[i][j]; if(j!=n-1) cout<<" "; else cout<<endl; } } } return 0; }