题解 P1588 【丢失的牛】

· · 题解

我的同学竟然在一篇题解里函数名用了我的名字，所以我在这篇题解里也要把他的名字作为函数名【手动滑稽】

这个人就是他，我同学

不说了，进入正题

这种题适合使用bfs,什么是bfs呢？

bfs,就是我们说的广度优先搜索，它与dfs是搜索中经常用到的。

dfs:

dfs就是深度优先搜索，它会把每一种可能都尝试一遍，通常我们使用它来求解连通块以及最短路之类的问题。

bfs:

bfs就是广度优先搜索，dfs相当于一条道走到黑，不撞南墙不回头。bfs则是把n步可以走到多少个点来求出来。求最短路问题时会经常用到它，因为它第一次走到这个点就是到这个点的最短路。

好了，开始进入这道题吧

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 5;//这是一个好习惯
struct node
{
    int x,ans;
}st;//st代表起点。
int t,n,m,a[N],tmpx;
queue<node> q;//建立一个队列来维护bfs
void wyz(int cow)
{
    while(!q.empty())//因为有多组数据，所以要记得清空队列
        q.pop();
    q.push(st);//st压入队列
    while(!q.empty())
    {
        if(a[cow] != -1)
        {
            printf("%d\n",a[cow]);//访问到时直接输出
            break;
        }
        node t = q.front();
        q.pop();
        for(int i = 1;i <= 3;i++)//这里我的方法比较傻，大家还可以再想想。
        {

            if(i == 1)
            {
                tmpx = t.x + 1;//向前走一步
                if(tmpx > N)//这里要注意，不加这个会re,而在本地是能通过的，因为本地给你自动分配了内存
                    continue;
                if(a[tmpx] != -1)
                    continue;
                a[tmpx] = t.ans + 1;
                q.push((node)
                {
                    tmpx,t.ans + 1
                });
            }
            else if(i == 2)
            {
                tmpx = t.x - 1;//向后退一步
                if(tmpx <= 0)
                    continue;
                if(a[tmpx] != -1)
                    continue;
                a[tmpx] = t.ans + 1;
                q.push((node)
                {
                    tmpx,t.ans + 1
                });
            }
            else
            {
                tmpx = t.x*2;//走到当前位置*2的地方
                if(tmpx > N)
                    continue;
                if(a[tmpx] != -1)
                    continue;
                a[tmpx] = t.ans + 1;
                q.push((node)
                {
                    tmpx,t.ans + 1
                });
            }
        }
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        st.x = n;
        st.ans = 0;
        memset(a,-1,sizeof(a));//注意数组初始化
        a[n] = 0;
        wyz(m);
    }
    return 0;
}

温馨提示：使用bfs时要记得判断问题边界哦

最后，不要抄袭。