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
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 Output4
*題意によると、この問題に直接反応するのは三度の木です.この木を遍歴するとステップ数が得られますが、ツリーを処理しないとタイムアウトします.他の問題は全部とても会いたいです.#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;
}