计蒜客题解——T1257：哆啦A梦的时光机

给定一个开始数据，然后按照下列规则，变成另外一个数据，最少需要几次：

规则1：数据 X 可以变为 X+1。

规则2：数据 X 可以变为 X-1。

规则3：数据 X 可以变为 2*X。

规则4：数据 X 如果是偶数，可以变为 X/2。

样例数据分析

我们就分析一组数据，我们选择 5 17 这组数据。问题就是从 5 开始，按照规则变成 17 需要最少几步。那么根据规则我们可以画出如下的一棵树：

从上图我们可以非常清晰的看出，从 5 变成 17，只需要 4 次。由于规则中有对称部分，规则 1 和规则 2 对称，规则 3 和规则 4 对称。因此 17 变为 5 也需要 4 次，这样输出答案为 8 次。

编程思路

从上图可以看出，这是一个典型的 BFS 题目，因为题目要求我们输出最小次数。因此我们可以写出一个大体框架。

1、读入数据。

2、从开始数据开始，进行 BFS 遍历，看到达结束数据需要几次。

技术细节

1、已知数据，如何按照规则变为下一个数据？

我比较傻，暂时没有想出统一代码，我就逐一编写规则。代码类似：

按照规则1，X+1，变化数据，并测试数据是否已经访问过。
按照规则2，X-1，变化数据，并测试数据是否已经访问过。
按照规则3，X*2，变化数据，并测试数据是否已经访问过。
按照规则4，如果是偶数，则X/2，变化数据，并测试数据是否已经访问过。

2、如何记录一个数据已经访问过？

第一次我想节约点空间，使用 unorderd_map 来记录访问性。定义方法如下：

unordered_map vis;

结果导致有 4 个样例超时，没有通过。主要 unorderd_map 内部是哈希表实现，相对比较耗时，导致了 TLE。

最后只要不考虑空间问题，直接定义如下：

const int MAXN = 1e6+2;
bool vis[MAXN];

AC 参考代码

#include using namespace std;typedef struct _POS {int value;int dis;
} POS;const int MAXN = 1e6+2;
bool vis[MAXN];//从st点开始到ed点
int bfs(int st, int ed, int dis) {memset(vis, 0, sizeof(vis));//初始化vis不能少queue q;POS now, next;now.value = st;now.dis   = dis;q.push(now);vis[st] = true;while (false==q.empty()) {now = q.front();q.pop();//判断是否终点if (now.value==ed) {return now.dis*2;}//规则1next.value = now.value+1;if (next.value>0 && next.value<1000000 && false==vis[next.value]) {next.dis = now.dis+1;q.push(next);vis[next.value] = true;}//规则2next.value = now.value-1;if (next.value>0 && next.value<1000000 && false==vis[next.value]) {next.dis = now.dis+1;q.push(next);vis[next.value] = true;}//规则3next.value = now.value*2;if (next.value>0 && next.value<1000000 && false==vis[next.value]) {next.dis = now.dis+1;q.push(next);vis[next.value] = true;}//规则4//偶数if (0==now.value%2) {next.value = now.value/2;if (next.value>0 && next.value<1000000 && false==vis[next.value]) {next.dis = now.dis+1;q.push(next);vis[next.value] = true;}            }}return 0;
}int main() {int n;cin >> n;for (int i=0; i>s>>t;cout<