题解 P2335 【[SDOI2005]位图】

BFS的套路 ~~这是一道完全相似的原题~~ 用一个数组dis[i][j]表示坐标为(i,j)的点离白点的最短距离。dis初始化为-1 每个白点入队时都将自己对应的dis位置设置为0.根据题意， 题目中两点距离的计算方式相当于“一个人从A点，每次只能向上下左右四个方向走一格，问走到B点要多少次？” 接着就对于每个要扩展的点，扩展出所有状态。设扩展出的新点坐标为(nx,ny), 如果 dis[nx][ny] != -1,则已经有更优解了（BFS的特性），故此点无需入队。nx，ny出界也无需入队。 否则， 赋值dis[nx][ny]，并将此点入队。 代码： ```cpp #include <bits/stdc++.h> using namespace std; int a[155][155],dis[155][155],f,e,n,m; //f:队首，e:队尾之后一个位置，队列范围为[f,e) struct Node{int x,y,cnt;}; Node q[100005]; //队列 int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};//四个方向 int main () { memset(dis,-1,sizeof(dis));//初始化 scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) { scanf("%d",&a[i][j]); if (a[i][j]) { dis[i][j] = 0; q[e++] = {i,j,0}; } } while (f != e) { Node nd = q[f++];//出队 for (int i = 0;i < 4;i++) { int nx = nd.x + dx[i],ny = nd.y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m || dis[nx][ny] != -1) //判断是否需入队 continue; dis[nx][ny] = nd.cnt + 1; q[e++] = {nx,ny,nd.cnt + 1};//入队 } } for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) printf("%d ",dis[i][j]); printf("\n"); } //输出 return 0; } ``` 好一道广搜