题解 P1588 【丢失的牛】

· · 题解

题目链接：传送门

思路：

这题可以用BFS来做，我们首先得构造隐式图

根据题意，JF每次可以前进一步、后退一步或者直接走到2*x的位置，每次花费的时间都一样

在广搜的时候我们只要把当前节点的前一个位置、后一个位置和第2*x的位置入队就好了

然后统计距离，不难理解，到达这些节点的步数是当前节点的步数+1

如果队首元素为终点位置，则结束搜索，输出到当前位置的步数

关于手写队列：

众所周知stl的常数都很大

我们可以用一个数组来实现队列，用两个变量l和r分别表示队首和队尾，队首变量++就相当于pop，队尾边量++就相当于push，这样可以有效防止爆队列，而且重设一下队首和队尾变量就相当于清空了整个队列。

优点：

常数小

缺点：

空间消耗较大，但是可以改成循环队列

Code: 
int q[N],l,r;//手写队列

代 码 放 送：

既然你能找到这题，我相信你能瞬间做出来的。

Code: 
#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,k,T,ans;
int vis[N],d[N],dx[3];
int q[N],l,r;//手写队列
void bfs(){
    while(l<=r){
        int x=q[l];
        if(x==k){printf("%d\n",d[l]);return;}
        dx[0]=x+1,dx[1]=x-1,dx[2]=x<<1;
        for(int i=0;i<3;i++)
            if(dx[i]>=0&&dx[i]<N&&!vis[dx[i]])
                q[++r]=dx[i],d[r]=d[l]+1,vis[dx[i]]=1;
        l++;
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));
        l=r=1;
        scanf("%d%d",&n,&k);
        q[l]=n;
        vis[n]=1;
        bfs();
    }
    return 0;
}