题解 P1588 【丢失的牛】

· · 题解

这一篇题解写给刚刚学习宽搜的同学，记得当时刚学时看题解基本都是一句话：这题裸的宽搜啊，当时一脸绝望。。。

本篇题解延续个人风格，细致的讲解：各位大佬可以跳过，直接看代码找本题坑点也行。

首先先来明确一下什么是宽搜？

通俗来说，宽搜就是从一个点开始扩展，将所能延伸到的点记录下来，当不能延伸时就对下一个点重复这个操作，直到找到最先满足条件的解为止（反正我是这么理解的。。。）

那么对于这一道题来说，一个点所能延伸出来的点只有+1，-1，*2，那么我们就可以开一个队列（手写也是可以的，但是为了省事就用STL吧。。。），从起点开始延伸，遇到没有走过的点就加入队列，并记录走了多少步，那么为什么走过的点不加呢？（因为如果之前走过，那么之前走肯定比现在走得到的解更优），当遇到第一个走到的位置达到终点是跳出并输出当时走了多少步即可。

差不多就这些了吧。。。

最后，附上本题代码（有详解）：

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
queue<int>q;
const int maxn= 1e5+5;
int dis[maxn];//dis表示走到目前位置最少走了多少步 
void bfs(int s,int y)
{
    int x;
    while(!q.empty())//多组询问常规清空操作 
    {
        q.pop();
    }
    memset(dis,0x5a5b5c4f,sizeof(dis));//初值设为inf，省去一个vis数组的空间 
    dis[s]=0;
    q.push(s);
    while(!q.empty())//bfs模板 
    {
        x=q.front();
        q.pop();
        if(x==y)//满足条件跳出 
        {
            printf("%d\n",dis[y]);
            return;
        }
        if(x+1<=maxn&&dis[x+1]==dis[0])//以dis[0]作为判断依据，也就是inf。判断该点是否走过，注意不要走出maxn 
        {
            dis[x+1]=dis[x]+1,q.push(x+1);
        }
        if(x-1>0&&dis[x-1]==dis[0])//x-1>0 比较显然吧，如果小于0你会RE，如果等于0你的dis[0]就会被更新，你整个程序就会崩掉 
        {
            dis[x-1]=dis[x]+1,q.push(x-1);
        }
        if(x*2<=maxn&&dis[x*2]==dis[0])//不复读了。。。 
        {
            dis[x*2]=dis[x]+1,q.push(x*2);
        }
    }
}
int main()
{
    int t;
    int x,y;
    scanf("%d",&t);
    for(int i=1; i<=t; i++)
    {
        scanf("%d%d",&x,&y);
        bfs(x,y);
    }
    return 0;
}