POJ3278---Catch That Cow

POJ3278—Catch That Cow

题目描述

农夫约翰已被告知逃亡牛的位置，并希望立即抓住她。他开始于一个点N（0≤ N≤100,000）和牛是在点K （0≤ K≤100,000），他们在同一条线上。农夫约翰有两种交通方式：步行和乘车。
行走：约翰可以在一分钟内从任意点X移动到X -1或X + 1 点
乘车：约翰可以在一分钟内从任意点X移动到点2× X .
如果母牛不知道它的追赶，根本不动，那么农夫约翰需要多长时间才能找回它？

输入

第1行：两个以空格分隔的整数：N和K

输出

第1行：农夫约翰用最少的时间（以分钟为单位）捉住逃犯。

输入样例

5 17

输出样例

4

思路分析

该题主要考察图的遍历
本题,JF每一步可能有三种走法,走过后做个标记.相当于先走图中的邻接点,再判断邻接点的邻接点.应采用广度优先.

1. 如果n>m,因为不可以向前乘车，只能向前一步一步的后退， 需要n-m步。否则执行(2)步;。
2. 从当前结点出发，广度优先搜索，每个结点可以扩展3个位置，判断该位置是否为牛的位置，如果是返回扩展走过的距离;否则，判断位置是否有效(未超界且未访问)，如果是则距离加1后，将位置入队。
3. 如果队列不空，一直广搜，直到找到牛的位置。

另外深度优先也可以入手,只是较难思考,思路如下:

1. 如果n>m,因为不可以向前乘车，只能向前一步一步的后退， 需要n-m步。否则执行(2)步;。
2. 如果1=0，则先走一步到1，n=l, 否则无法乘车走两倍，0的两倍还是0。
3. 然后从m向n搜索，t=m, 深度优先搜索:
   如果t为偶数，则比较向前乘车到t/2、 一步一步向前走哪种方案步数最少，取最小值。
   如果t为奇数，则比较向前一步、向后一步、一步一步向前走哪种方案步数最少，取最小值;
   如果t跑到了n的前面，则比较从t向后走到n (步数n-t),还是乘车到2t, 再向前回退到n (步数2t-n+1)，哪种方案步数最少.

参考代码1—广度优先

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 100010;
int n, k;
bool vis[maxn];//存储是否访问过 只表示图中已经存在该点,后续不需要再次生成/访问.并不表示已经进行判断了.
int step[maxn];//存储走过步数
void solve()
{
   
	queue<int> Q;
	vis[n] = 1;
	step[n] = 0;
	Q.push(n);//起点入队
	while (!Q.empty())
	{
   
		int head = Q.front();
		Q.pop();
		if (head == k)
		{
   
			cout << step[head] << endl;
			return;
		}
		//访问其他可能的三个点.
		int x = head + 1;
		if (x <= 100000 && !vis[x])
		{
   
			step[x] = step[head] + 1;//步数+1
			vis[x] = true;
			Q.push(x);
		}
		x = head - 1;
		if (x >= 0 && !vis[x])
		{
   
			step[x] = step[head] + 1;
			vis[x] = true;
			Q.push(x);
		}
		x = head * 2;
		if (x <= 100000 && !vis[x])
		{
   
			step[x] = step[head] + 1;
			vis[x] = true;
			Q.push(x);
		}
	}
}
int main()
{
   
	while (cin >> n >> k)
	{
   
		if (n >= k)
		{
   
			cout << n - k << endl;
			continue;
		}
		memset(vis, false, sizeof(vis));//初始化数组
		memset(step, 0, sizeof(step));
		solve();
	}
	return 0;
}

参考代码2----深度优先

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;

int dfs(int t)
{
   
	if(t<=n)
		if(n-t<t*2-n+1)
			return n-t;
		else
			return t*2-n+1;
	if(t%2==1)
		return min(min(dfs(t+1)+1,dfs(t-1)+1),t-n);
	else
		return min(dfs(t/2)+1,t-n);
}

int main()
{
   
	while(cin>>n>>m)
	{
   
		if(n>m)
		{
   
			cout<<n-m<<endl;
			continue;
		}
		int t=m;
		int ans=0;
		if(n==0)//这段很重要
		{
   
			n=1;
			ans=1;
		}
		ans+=dfs(t);
		cout<<ans<<endl;
	}
	return 0;
}