♥POJ 3278-Catch That Cow【搜索】

淩亂°似流年 2022-08-20 13:28 116阅读 0赞

C - Catch That Cow

**Crawling in process...** **Crawling failed**

**Time Limit:** 2000MS **Memory Limit:** 65536KB **64bit IO Format:** %I64d & %I64u

Submit [ Status][Status] [ Practice][Practice] [ POJ 3278][POJ 3278]

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

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.

解题思路：

题目大意就是有一个农夫和一头牛，在n，k，农夫想要到牛哪里，有两种移动方式，第一是坐标加1，第二是坐标乘2。注意搜索时超内存。

#include<stdio.h>
    #include<string.h>
    #include<queue>
    #include<algorithm> 
    using namespace std;
    struct node
    {
    	int x,step;
    };
    int flag[100005];
    bool judge(node p)
    {
    	if(p.x<0||p.x>100000||p.step>flag[p.x])//判断到这一点时间是不是最短的 是否更新 
    	return false;
    	return true;
    }
    int main()
    {
    	int n,k;
    	while(scanf("%d%d",&n,&k)!=EOF)
    	{
    		if(n==k)
    		{
    			printf("0\n");
    			continue;
    		}
    		memset(flag,0x7f,sizeof(flag));
    		node ks;
    		ks.x=n;
    		ks.step=0;
    		flag[ks.x]=0;
    		queue<node>q;
    		q.push(ks);
    		int wc=0;
    		while(!q.empty())
    		{
    			node end,end2;
    			end2=q.front();
    			q.pop();
    			for(int i=0;i<3;i++)
    			{
    				end=end2;
    				if(i==0)
    				{
    					end.x++;
    				}
    				if(i==1)
    				{
    					end.x*=2;
    				}
    				if(i==2)
    				{
    					end.x--;
    				}
    				end.step=end2.step+1;
    				if(!judge(end))//如果不判断一下   直接进队是会超内存  各种超内存 
    				{
    					continue;
    				}
    				if(end.x==k)
    				{
    					printf("%d\n",end.step);
    					wc=1;
    					break;
    				}
    				flag[end.x]=end.step;
    				q.push(end);
    			}
    			if(wc==1)
    			break;
    		}
    	} 
    	return 0;
    }

[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=94505#status//C/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=15204
[POJ 3278]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15204