[kuangbin带你飞]专题一 简单搜索 C

C - Catch That Cow[POJ - 3278]

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?

Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input
5 17
Sample Output
4

Hint
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.

• re了一次，因为以为这题没有上界，但是没有考虑到在check的过程中会超过visited的最大长度。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int visited[100010]; 
int K,N;

struct node{
    int pos;
    int cnt;
};

int check(node checknode){
    if(checknode.pos<0||checknode.pos>100000||visited[checknode.pos]){
        return 0;
    }
    return 1;
}

int bfs(node st){
    queue<node> Q;
    Q.push(st);
    visited[st.pos] = 1;
    while(!Q.empty()){
        node nownode;
        node nextnode;
        nownode = Q.front();Q.pop();
        if(nownode.pos == K){
            return nownode.cnt;
        }
        nextnode.cnt = nownode.cnt+1;
        nextnode.pos = nownode.pos+1;
        if(check(nextnode)){
            visited[nextnode.pos] =1;
            Q.push(nextnode);
        }
        nextnode.pos = nownode.pos-1;
        if(check(nextnode)){
            visited[nextnode.pos] =1;
            Q.push(nextnode);
        }
        nextnode.pos = nownode.pos*2;
        if(check(nextnode)){
            visited[nextnode.pos] =1;
            Q.push(nextnode);
        }
             
    }
}

int main(){
    cin>>N>>K;
    node st;
    st.pos = N;
    st.cnt = 0;
    int ans;
    ans = bfs(st);
    cout<<ans<<endl;
    return 0;
    
}