题意
给出你一条直线，和你在直线上的位置以及牛在直线上的位置，你每一次操作可以左移一个单位，或者右移一个单位，或者把你当前的坐标直接乘2作为你的新坐标。你要求出你最少要经过多少次操作才能正好移动到牛的位置上。
思路
不典型的最短路问题数据较小时可以使用BFS解决，不过本题不能盲目DFS，要注意排除掉已经不可能产生优解／更优解的情况，在这里我剔除掉的情况是：
- 当前走的步数已经大于等于当前最优解了
- 当前的位置已经小于0了
- 当前的位置与牛的距离已经超过了开始时与牛的距离（合理的最坏情况下的距离）。
- 当超过了牛的位置时，只能选择回退，如果接下来的回退所消耗的时间加上现在已经消耗的时间已经不可能再产生更优解
上述这种在搜索途中将一些预计不能产生优解／更优解的情况排除掉的方法也称为“剪枝”，这是暴力搜索中很常用、很重要的一种优化手段。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; struct node{ int pos; int cnt; }; int main(){ int n = 0,k = 0; while (cin >> n >> k) { queue<node> q; node init; init.pos = n; init.cnt = 0; q.push(init); int res = abs(n-k); int times = 0; bool vis[100005]; memset(vis,0,sizeof(vis)); while (!q.empty()){ times++; node now = q.front(); int nowpos = now.pos; q.pop(); if(now.cnt >= res || nowpos < 0 || nowpos > 100000) continue; if(vis[nowpos]) continue; vis[nowpos] = true; if(now.pos > k){ if(now.pos - k > res - now.cnt) continue; now.pos--; now.cnt++; q.push(now); continue; } if(now.pos == k){ res = min(now.cnt,res); continue; } if(now.pos < k){ now.cnt++; if(now.pos > 0){ now.pos = nowpos*2; q.push(now); } now.pos = nowpos+1; q.push(now); now.pos = nowpos-1; q.push(now); } } cout << res << endl; //cout << "time:" << times << endl; } } |
