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
思路1:BFS
本题,JF每一步可能有三种走法,走过后做个标记.然后继续往后寻找知道找到为止.
如果n>m,因为不可以向前乘车，只能向前一步一步的后退， 需要n-m步。否则执行(2)步;。
从当前结点出发，广度优先搜索，每个结点可以扩展3个位置，判断该位置是否为牛的位置，如果是返回扩展走过的距离;否则，判断位置是否有效(未超界且未访问)，如果是则距离加1后，将位置入队。
另外深度优先也可以入手,只是较难思考,思路如下(了解):
如果n>m,因为不可以向前乘车，只能向前一步一步的后退， 需要n-m步。否则执行(2)步;。
如果1=0，则先走一步到1，n=l, 否则无法乘车走两倍，0的两倍还是0。
然后从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; }
