Crawling in process... Crawling failed Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
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
Output
Sample Input
5 17
Sample Output
4
Hint
题意：给你n,m两个数，如何用最少操作次数把n变成m。n只能加一减一或者乘2。
范围0到100000
直接bfs，越界或者搜过的数排除掉。
#include <stdio.h>
#define inf 0x6ffff
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
struct node
{
int x;
int step;
}
;
int n,m;
int flag[100005];
int bfs(int x)
{
int i;
queue<node>q;
node st,ed;
flag[x]=1;
st.x=x;
st.step=0;
q.push(st);
while(!q.empty())
{
st=q.front();
q.pop();
if(st.x==m )
return st.step;
for(i=1;i<=3;i++)
{
if(i==1)
ed.x=st.x+1;
if(i==2)
ed.x=st.x-1;
if(i==3)
ed.x=st.x*2;
if(ed.x>100000 ||ed.x<0 ||flag[ed.x]) //搜过的数标记为一，越界排除。
continue;
ed.step=st.step+1;
flag[ed.x]=1;
q.push(ed);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(flag,0,sizeof(flag));
if(n==m)
printf("0\n");
else
{
int ans=bfs(n);
printf("%d\n",ans);
}
}
return 0;
}
原文：http://blog.csdn.net/sky_miange/article/details/43534915