题解 P2873 【[USACO07DEC]Mud Puddles S】

· · 题解

这题吸引我的地方竟然是它的题目。。。

Mud Puddles

一下我就想到了

大家都喜欢跳泥坑！！！

好了我们言归正传

这题其实是个裸的bfs

一道很好的练手题

先来看看题目中的重点：

“FJ的屋子在平面坐标(0, 0)的位置，贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。”

what？负数？USACO您在逗我？

其实面对负数，我们只要把坐标加上500即可，同时也不要忘记存储地图的数组也要相应增加大小。

“最少要走多少路才能到贝茜所在的牛棚呢？”

这。。。说的要多明显有多明显，就差一句“这题请用宽搜解决”。

“你可以认为从FJ的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。”

这就是说此题一定有解，无需考虑走不通的情况。

好的我们先把代码贴上来

#include<bits/stdc++.h>
using namespace std;

int X,Y,n,dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//dir数组存储四个方向
bool mmap[1005][1005];//存储地图（注意这里不是500而是1000）
struct node{
    int x,y,sum;
};//定义结构体，x表示横坐标，y表示纵坐标，sum表示到这个点所需步数
queue <node> qwq;//当然要符合我们小猪佩奇的可爱气质啦

int bfs ()//宽搜
{
    while (!qwq.empty())//队列非空
    {
        int xx,yy,s;
        xx=qwq.front().x;
        yy=qwq.front().y;
        s=qwq.front().sum;//取队首元素进行扩展
        for (int i=0;i<4;i++)//4个方向
        {
            int nx=xx+dir[i][0],
                ny=yy+dir[i][1];//扩展
            if (nx==X && ny==Y)//如果到达目的地
            {
                while (!qwq.empty())
                  qwq.pop();//清空队列
                return s+1;//返回值
            }
            else//没有到达目的地
            {
                if (!mmap[nx][ny])//可以走（即这里不是泥坑）
                {
                    mmap[nx][ny]=true;//把这里标记成走过的
                    //其实可以再开一个vis数组，但对于这题完全没必要
                    qwq.push({nx,ny,s+1});//入队
                }
            }
        }
        qwq.pop();//出队
    }
}

int main()
{
    scanf ("%d%d%d",&X,&Y,&n);//输入
    memset (mmap,false,sizeof (mmap));//初始化
    X+=500;  Y+=500;//重要！！！一定要加500！！！
    qwq.push({500,500,0});//初始情况入队
    for (int i=1;i<=n;i++)
    {
        int a,b;
        scanf ("%d%d",&a,&b);
        a+=500; b+=500;//坐标加500
        mmap[a][b]=true;//标记泥坑
    }
    printf ("%d\n",bfs ());//输出
    return 0;//完结撒花
}

另附宽搜模板

初始状态入队;       
while(队列不为空)
{
    取队首元素进行扩展; 
    for(对所有可能的拓展状态)
    {
        if(新状态合法)
            入队;
        if(当前状态是目标状态)   
            处理(输出解或比较解的优劣); 
    }
    队首结点扩展完毕，出队; 
}