Poj 3278 Catch That Cow （BFS+队列）

accbulb / 2024-02-03 / 原文

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,k,line[N],way;
struct node{int loc,step;};
queue<node> q;
void BFS(int n,int k){
    while(!q.empty()) q.pop();
    node start,next;
    start.loc=n;
    start.step=0;
    q.push(start);
    line[start.loc]=1;
    while(!q.empty()){
        start=q.front();
        q.pop();
        if(start.loc==k){
            cout<<start.step<<endl;
            break;
        }
        way=start.loc*2;
        if(way<=100000&&!line[way]){
            next.loc=way;
            line[way]=1;
            next.step=start.step+1;
            q.push(next);
        }
        way=start.loc+1;
        if(way<=100000&&!line[way]){
            next.loc=way;
            line[way]=1;
            next.step=start.step+1;
            q.push(next);
        }
        way=start.loc-1;
        if(way<=100000&&!line[way]){
            next.loc=way;
            line[way]=1;
            next.step=start.step+1;
            q.push(next);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(cin>>n>>k){
        memset(line,0,sizeof(line));
        BFS(n,k);
    }
    return 0;
}