Description
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
Input
第一行两个整数n m ( 1 ≤ n，m ≤ 100 )
接下来输入 n行 m列 的二维数组。
3 3
0 0 0
0 1 0
0 0 0
Output
输出每个元素到最近的 0 的距离。
0 0 0
0 1 0
0 0 0
Sample Input
3 3
0 0 0
0 1 0
1 1 1
Sample Output
0 0 0
0 1 0
1 2 1
用BFS
1 #include<iostream>
2 #include<queue>
3 using namespace std;
4 int m,n;
5 int a[103][103];
6 int dir[4][2]={1,0,0,1,-1,0,0,-1};//转向数组
7 int book[103][103];//标记数组
8 struct node{//定义结构体
9 int x;
10 int y;
11 int step;
12 node(int xx,int yy,int step1):x(xx),y(yy),step(step1){}//构造函数
13 };
14 queue<node> q;//队列
15 void bfs(){
16 while(!q.empty()){//只要队列不为空
17 node s=q.front();//取队列第一个元素
18 for(int i=0;i<4;i++){//向该元素的四个方向搜索
19 int dx=s.x+dir[i][0];//新的x坐标
20 int dy=s.y+dir[i][1];//新的y坐标
21 if(dx>=1&&dx<=m&&dy>=1&&dy<=n&&a[dx][dy]==1&&book[dx][dy]==0){//如果在地图范围内，并且没有被标记过，并且格子值还为1
22 book[dx][dy]=1;//标记该格子
23 q.push(node(dx,dy,s.step+1));//把该格子加入队列
24 a[dx][dy]=s.step+1;//把这个格子的值更新为它距离0最近的距离
25 }
26 }
27 q.pop();//弹出该元素
28 }
29 }
30 int main(){
31 scanf("%d%d",&m,&n);
32 for(int i=1;i<=m;i++){
33 for(int j=1;j<=n;j++){
34 scanf("%d",&a[i][j]);
35 if(a[i][j]==0)//先把值为0的格子加入队列
36 q.push(node(i,j,0));
37 }
38 }
39 bfs();
40 for(int i=1;i<=m;i++){
41 for(int j=1;j<=n;j++){
42 printf("%d ",a[i][j]);
43 }
44 printf("
");
45 }
46 return 0;
47 }