题目:
抓住那头牛
Description 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
Input 两个整数,N和K。
Output 一个整数,农夫抓到牛所要花费的最小分钟数。
Sample Input5 17
Sample Output4
我的错误代码:
#include<iostream>
#include<cstring>
using namespace std;
long long n,k,a[100005]={0};
struct point{int x,c;}q[300001];
void bfs()
{
int n1,i,left,right;
left=1;
right=1;
a[n]=1;
q[1].c=0;
q[1].x=n;
while(left<=right)
{
for(i=1;i<=3;i++)
{
if(i==1)
{
n1=q[left].x+1;
if(a[n1]!=1)
{
a[n1]=1;
right++;
q[right].x=n1;
q[right].c=q[left].c+1;
if(q[right].x==k){cout<<q[right].c<<endl;return;}
}
}
if(i==2)
{
n1=q[left].x-1;
if(a[n1]!=1)
{
a[n1]=1;
right++;
q[right].x=n1;
q[right].c=q[left].c+1;
if(q[right].x==k){cout<<q[right].c<<endl;return;}
}
}
if(i==3)
{
n1=q[left].x*2;
if(a[n1]!=1)
{
a[n1]=1;
right++;
q[right].x=n1;
q[right].c=q[left].c+1;
if(q[right].x==k){cout<<q[right].c<<endl;return;}
}
}
}
left++;
}
}
int main()
{
cin>>n>>k;
bfs();
return 0;
}
麻烦大佬们了!
抓住那头牛
Description 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
Input 两个整数,N和K。
Output 一个整数,农夫抓到牛所要花费的最小分钟数。
Sample Input5 17
Sample Output4
我的错误代码:
#include<iostream>
#include<cstring>
using namespace std;
long long n,k,a[100005]={0};
struct point{int x,c;}q[300001];
void bfs()
{
int n1,i,left,right;
left=1;
right=1;
a[n]=1;
q[1].c=0;
q[1].x=n;
while(left<=right)
{
for(i=1;i<=3;i++)
{
if(i==1)
{
n1=q[left].x+1;
if(a[n1]!=1)
{
a[n1]=1;
right++;
q[right].x=n1;
q[right].c=q[left].c+1;
if(q[right].x==k){cout<<q[right].c<<endl;return;}
}
}
if(i==2)
{
n1=q[left].x-1;
if(a[n1]!=1)
{
a[n1]=1;
right++;
q[right].x=n1;
q[right].c=q[left].c+1;
if(q[right].x==k){cout<<q[right].c<<endl;return;}
}
}
if(i==3)
{
n1=q[left].x*2;
if(a[n1]!=1)
{
a[n1]=1;
right++;
q[right].x=n1;
q[right].c=q[left].c+1;
if(q[right].x==k){cout<<q[right].c<<endl;return;}
}
}
}
left++;
}
}
int main()
{
cin>>n>>k;
bfs();
return 0;
}
麻烦大佬们了!