希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

POJ3278_bfs简单题

/*
bfs+剪枝典型简单题,注意此题设置的方向动态确定,且要判断,是否左大于右。
*/

#include 
<iostream>
#include 
<cstdio>
#include 
<algorithm>
#include 
<memory.h>
#include 
<cmath>
#include 
<bitset>
#include 
<queue>
#include 
<vector>
using namespace std;

const int MAXN =100400;
const int INF =0x4ffffff;
#define CLR(x,y) memset(x,y,sizeof(x))
#define ADD(x) x=((x+1)&BORDER)
#define IN(x) scanf("%d",&x)
#define OUT(x) printf("%d\n",x)
#define MIN(m,v) (m)<(v)?(m):(v)
#define MAX(m,v) (m)>(v)?(m):(v)
#define ABS(x) ((x)>0?(x):-(x))
struct node{
    
int x;
    
int step;
    node():x(
0),step(0){}
}
;
int vis[MAXN*2];
int sum,n,ans;
int main()
{
    
int n,k,i,min=999999;
    
int dir[4]={-1,1};
    node start,end,tmp,next;
    queue
<node> que;
    scanf(
"%d%d",&start.x,&end.x);
    que.push(start);
    vis[start.x]
=1;
    
if(start.x>end.x)min=start.x-end.x;
    
else
    
while(!que.empty())
    
{
        tmp
=que.front();
        que.pop();
        dir[
2]=tmp.x;
        
//dir[3]=2*tmp.x;
        for(i=0;i<3;++i)
        
{
            next.x
=tmp.x+dir[i];
            
if(next.x>=0&&next.x<=end.x*3&&next.x<=MAXN&&tmp.step<min&&!vis[next.x])
            
{
                next.step
=tmp.step+1;
                
if(next.x==end.x)min=min>next.step?next.step:min;
                    que.push(next);
                    vis[next.x]
=1;
            }

        }

    }

            memset(vis,
0,sizeof(vis));
            
if(min==999999)min=0;
        printf(
"%d\n",min);
        min
=999999;
}

Catch That Cow
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 23446 Accepted: 7185

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

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

posted on 2011-06-05 00:19 拥梦的小鱼 阅读(432) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理