1013 [USACO 2007 Ope S]Catch That Cow bfs 剪枝

标签：剪枝 cow Cow point int USACO vis Farmer John

 链接：https://ac.nowcoder.com/acm/contest/26077/1013
来源：牛客网

题目描述

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 <= N <= 100,000) on a number line and the cow is at a point K (0 <= K <= 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
Walking: FJ can move from any point X to the points X-1 or X+1 in a single minute Teleporting: FJ can move from any point X to the point 2*X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

输入描述:

Line 1: Two space-separated integers: N and K

输出描述:

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

示例1

输入

复制 5 17

5 17

输出

复制 4

4

说明

Farmer John starts at point 5 and the fugitive cow is at point 17.
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

分析

题目范围比较小，所以直接bfs+剪枝就可以做了。但是感觉应该是位运算的结论题。也不对，三种操作。+1 和 *2 倒是可以直接做，-1

//-------------------------代码----------------------------

//#define int ll
const int N = 2e5+10;
int n,m,k;
int vis[N];
void bfs(int u) {
    queue<int> q;
    q.push(u);
    vis[u] = 0;
    while(q.size()) {
        auto t = q.front();q.pop();
        if(t == k) {
            cout<<vis[k]<<endl;
            rt;
        }
        if(t-1>=0 && !vis[t-1])q.push(t-1),vis[t-1] = vis[t]+1;
        if(t+1<=k && !vis[t+1])q.push(t+1),vis[t+1] = vis[t] + 1;
        if(t*2<=2*k && !vis[t*2])q.push(t*2),vis[t*2] = vis[t]+1;
        
    }
}

void solve()
{
//    cin>>n>>m;
    cin>>n>>k;
    if(k <= n) {
        cout<<n - k<<endl;
        rt;
    }
    bfs(n);
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

标签：剪枝,cow,Cow,point,int,USACO,vis,Farmer,John
From： https://www.cnblogs.com/er007/p/16599808.html