题解 P2335 【[SDOI2005]位图】

2018-07-22 08:07:29


BFS的套路 这是一道完全相似的原题

用一个数组dis[i][j]表示坐标为(i,j)的点离白点的最短距离。dis初始化为-1

每个白点入队时都将自己对应的dis位置设置为0.根据题意, 题目中两点距离的计算方式相当于“一个人从A点,每次只能向上下左右四个方向走一格,问走到B点要多少次?”

接着就对于每个要扩展的点,扩展出所有状态。设扩展出的新点坐标为(nx,ny),

如果

dis[nx][ny] != -1,则已经有更优解了(BFS的特性),故此点无需入队。nx,ny出界也无需入队。

否则,

赋值dis[nx][ny],并将此点入队。

代码:

#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;
}

好一道广搜