给定一个N x M的01矩阵，其中1表示陆地，0表示水域。对于每一个位置，求出它距离最近的水域的距离是多少。
矩阵中每个位置与它上下左右相邻的格子距离为1。
Input 第一行包含两个整数，N和M。
以下N行每行M个0或者1，代表地图。
数据保证至少有1块水域。
对于30%的数据，1 <= N, M <= 100
对于100%的数据，1 <= N, M <= 800
Output 输出N行，每行M个空格分隔的整数。每个整数表示该位置距离最近的水域的距离。
Sample Input
4 4 0110 1111 1111 0110
Sample Output
0 1 1 0 1 2 2 1 1 2 2 1 0 1 1 0
题意很容易理解的，这里就不说了，这是一道广搜题，但需要调整搜的方法
最初思路：陆地搜水域，进行一个一个广搜，就超时了 其实仔细一想，假如一张图就右下角是水域，其它的全是陆地， 这样的广搜也是超级费时间的 接下来的思路：依然是广搜，但不一样的是只需把图搜一遍即可。 方法是利用水域搜水，你可能觉得和上一个方法是一样的操作，其实是不一样的 流程： 把所有的水域放入队列中，然后利用每一个水域去寻找该水域四周的陆地， 如果说该水域在一步的情况下没有找到陆地，那该水域就没有用处了，就可以被踢出队列了， 为什么这么说呢，你想想看，该水域的四周也是水域，陆地要寻找水域肯定会先找到 它四周的水域啊。 如果找到了陆地，那可给该陆地赋值所用的步数，其它的陆地可用该陆地去寻找,为什么呢， 因为该陆地最开始的地方是一条水域的，这就相当于一条水域后面接了一大串的陆地假如是4*4，里面有4个水域，12个陆地吧，就可能会出现这样的图
水域1----------->陆地4-------->陆地8---------->陆地12----------->陆地6 1步2步3步4步可到达水域（4个陆地）
水域2----------->陆地1-------->陆地3---------->陆地5------------>陆地7------->陆地9----------->陆地11------->陆地2 1步2步3步4步5步6步7步可到达水域（7个陆地）
水域3--------->水域10 一步可到达水域（1个陆地）
水域4 什么也没有 0个陆地
这就是利用广搜所能形成的路径
代码
#include<stdio.h> #include<queue> #include<string.h> #include<algorithm> using namespace std; int n,m; char e[880][880]; int a[880][880]; int to[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; struct Node{ int x,y,s; }u,v; queue<Node> q; void bfs() { int i,tx,ty; while(!q.empty()) { u=q.front(); q.pop(); for(i=0;i<4;i++) { tx=u.x+to[i][0]; ty=u.y+to[i][1]; if(tx<0||tx>=n||ty<0||ty>=m) continue; if(a[tx][ty]==-1)//进过队列的就不用再进了 { v.x=tx; v.y=ty; v.s=u.s+1; a[tx][ty]=v.s; q.push(v);//每个水在一步之内可达到的陆地才能进队列,而且同一个陆地只能进队列一遍，水全部出列队了便可依靠队列中的陆地找陆地，因为每个陆地都会在源点有一个水 } } } } int main() { while(~scanf("%d %d",&n,&m)) { memset(a,-1,sizeof(a)); int i,j; for(i=0;i<n;i++) scanf("%s",e[i]); for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(e[i][j]=='0') { a[i][j]=0; u.x=i; u.y=j; u.s=0; q.push(u);//所有的水都进队列 } } } bfs(); for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(j==0) printf("%d",a[i][j]); else printf(" %d",a[i][j]); } printf("\n"); } } return 0; }