HDOJ-三部曲一(搜索、数学)-1006- Catch That Cow

刺骨的言语ヽ痛彻心扉 2021-12-11 12:31 185阅读 0赞

Catch That Cow

##### Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other) #####

##### Total Submission(s) : 48   Accepted Submission(s) : 16 #####

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

Source

PKU

这道题是到BFS水题，不过我在这道题上re了很多次。。。原因是我没有剪枝。

#include<iostream>
    #include<cstring>
    using namespace std;
    int que[1000001];                        //数组要开大谢；大数组用全局变量开，不能再函数里开。
    int step[1000001]={0};   
    bool f[1000001]={false};
    int n,k;
    
    int BFS()
    {
    	int front=0,rear=1;
    	que[0]=n;
    	step[0]=0;
    	f[n]=true;
    	if(que[front]==k)
    		return step[front];
    	while(front<rear)
    	{
    		if(que[front]<k&&!f[que[front]+1])   //只有当前的数比k小时，加一才能更接近k。
    		{
    			que[rear]=que[front]+1;
    			step[rear]=step[front]+1;
    			f[que[rear]]=true;
    			if(que[rear]==k)
    				return step[rear];
    			rear++;
    		}
    		if(que[front]-1>=0&&!f[que[front]-1])  //数组不能越界
    		{
    			que[rear]=que[front]-1;
    			step[rear]=step[front]+1;
    			f[que[rear]]=true;
    			if(que[rear]==k)
    				return step[rear];
    			rear++;
    		}
    		if(que[front]<k&&!f[que[front]*2])  //只有当前的数比k小时，乘2才有可能更接近k。
    		{
    			que[rear]=que[front]*2;
    			step[rear]=step[front]+1;			
    			f[que[rear]]=true;
    			if(que[rear]==k)
    				return step[rear];
    			rear++;
    		}
    		front++;
    	}
    }
    
    int main()
    {
    	while(cin>>n>>k)
    	{
    		memset(que,0,sizeof(que));
    		memset(step,0,sizeof(step));
    		memset(f,false,sizeof(f));
    		cout<<BFS()<<endl;	
    	}
    }

转载于:https://www.cnblogs.com/aljxy/p/3335636.html