Catch That Cow(枝切り防止タイムアウト)

2062 ワード

Problem Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediatley.He starts at a point N(0≦N≦100,000)on a number line and the cow isa point K(0≦K≦100,000)on the same number line.Farmer John has two modes of transport: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 then move point X× X in a single minute.If the cow、unaware of its purrsuit、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 taes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
*題意によると、この問題に直接反応するのは三度の木です.この木を遍歴するとステップ数が得られますが、ツリーを処理しないとタイムアウトします.他の問題は全部とても会いたいです.
#include
#include
#include
using namespace std;
typedef struct node{
    int data;
    int ceng;
}Tree;
bool vis[100000];
queue  q;
int n,k;
void bfs(){
    Tree n;
    while(q.front().data!=k){
        int a=q.front().data;
        int b=q.front().ceng;
        n.data=a+1;
        n.ceng=b+1;
        if(n.data>=0&&n.data<=100000&&vis[n.data]==false){//         ,                   。
        q.push(n);                                           //          
        vis[n.data]=true;
        }
        n.data=a-1;
        n.ceng=b+1;
        if(n.data>=0&&n.data<=100000&&vis[n.data]==false){
        q.push(n);
        vis[n.data]=true;
        }
        n.data=a*2;
        n.ceng=b+1;
        if(n.data>=0&&n.data<=100000&&vis[n.data]==false){
        q.push(n);
        vis[n.data]=true;
        }
        q.pop();
    }
    cout<>n>>k;
    Tree t;
    memset(vis,false,sizeof(vis));
    t.ceng=0;
    t.data=n;
    q.push(t);
    bfs();
    return 0;
}