C语言BFS(3)___Catch That Cow(Hdu 2717)

80 阅读 0 评论 53 点赞

我是靠谱客的博主殷勤红牛，最近开发中收集的这篇文章主要介绍C语言BFS(3)___Catch That Cow(Hdu 2717)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem 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

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

题目大概意思：在一条道上，每个点x可以一步到 x-1 , x+1 , 2*x 这三个点,输入两个点,问最短几步可以到达.

简单的BFS,除了队列大小开合适外其他没什么要注意的.

#include <stdio.h>
#include <string.h>
struct Team
{
int x,s;
}team[1000000];
//两个数组不要开小了
int book[200000];
int main()
{
int flag,left,right;
int head,tail;
while(scanf("%d%d",&left,&right)!=EOF)
{
flag=0;
if(left==right)
{
printf("0n");
continue;
}
if(left>right)
{
printf("%dn",left-right);
continue;
}
memset(book,0,sizeof(book));
head=tail=0;
team[tail].s=0;
team[tail++].x=left;
book[left]=1;
int m=right-left;
while(head<tail)
{
if(team[head].s>m)
//剪枝
{
head++;
continue;
}
if(team[head].x>1&&!book[team[head].x-1])
{
team[tail].s=team[head].s+1;
team[tail++].x=team[head].x-1;
book[team[head].x-1]=1;
}
if(team[head].x<200000&&!book[team[head].x+1])
{
team[tail].s=team[head].s+1;
team[tail++].x=team[head].x+1;
book[team[head].x+1]=1;
}
if(team[head].x<100000&&!book[2*team[head].x])
{
team[tail].s=team[head].s+1;
team[tail++].x=2*team[head].x;
book[2*team[head].x]=1;
}
if(team[head].x-1==right||team[head].x+1==right||team[head].x*2==right)
{
printf("%dn",team[head].s+1);
flag=1;
break;
}
head++;
}
}
return 0;
}