HDU - 2717

大概是自己第一次在图之外用搜索吧(wwww
要是早点做过的话可能蓝桥省赛的那个记忆化搜索就能a出来了hhh

https://vjudge.net/problem/HDU-2717#author=shiyifan（这是hdu源链接，交不了）

https://vjudge.net/contest/476730#status/weixinjie/C/0/（不知道为啥东北师范的训练还能交，补了之后ac了）

题目

农场主约翰已被告知一头逃亡母牛的位置，他想立即抓住她。他从一条数线上的点N(0≤N≤100,000）开始，而cow在同一条数线上的点K(0≤K≤100,000）。农夫约翰有两种交通方式：步行和传送。 *步行：FJ可以在一分钟内从任何X点移动到X-1或X+1点 *传送：FJ可以在一分钟内从任意X点移动到2×X点。 如果这头母牛没有意识到它的追求，根本不动，农夫约翰需要多长时间才能找回它？

输入

第1行：两个空格分隔的整数：N和K（多组输入）

输出

第1行：农场主约翰抓住逃亡的母牛所需的最少时间，以分钟为单位。

样例

输入样例1

5 17

输出样例1

4

分析

从n开始跑到k，有n+1、n-1、n*2这三种方式

从输入开始分类讨论，当n大于等于k时直接输出n-k的值

当n小于k时，对三种移动方式进行bfs

bfs的原理就是把n移动后的三个数字放入队列中，再对这三个数做判断

那么就要判断当前这个数有没有被访问过，则建立一个2max的数组（n取到最大时，进行n2也不会溢出）

如果没有溢出且n移动后依然不等于k；就给步数加一并压入队列

如何实现？当然是结构体，结构体包括两个整数：n，表示数字；step，表示步数

当n移动后与k相等，就输出now.step

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#define maxx 100005
using namespace std;

struct nub {//储存这个数字的结构体
	int n;
	int step;
};

int fl[maxx * 2];
int main() {
	int n, k;
	while (scanf("%d %d", &n, &k) != EOF) {
		int i;
		queue <nub> q;//建立用于bfs的队列
		for (i = 0; i < maxx * 2 - 5; i++) {
			fl[i] = 1;//首先将用于标记的数组初始化为全部可访问
		}
		fl[n] = 0;
		if (n > k) {//n大于等于k时直接输出n-k，n==k的特判其实没必要但懒得改了 .U^U.
			printf("%d\n", n - k);
		} else if (n == k) {
			cout << 0 << endl;
		} else {
			struct nub fir;//定义做出的数的结构体(first)
			fir.n = n;//数字初始化为n
			fir.step = 0;//步数初始化为0
			q.push(fir);//把第一个数压入队列
			while (!q.empty()) {//当不为空时循环
				struct nub now;//当前数字结构体
				now = q.front();q.pop();//从队列取出数字放入now
				if (now.n == k) {//如果now.n与k相等，直接输出步数
					printf("%d\n", now.step);
					break;
				}
				if (now.n>=0&&n + 1 <= 100000) {//这里需要判断移动后的数在0和max之间，一开始忘了光wa
					if (fl[now.n + 1]) {
						fl [now.n + 1] = 0;//满足条件后先标记，省着忘了
						struct nub pp;
						pp.n = now.n + 1;//把移动后的数压入结构体
						pp.step = now.step + 1;//步数加一
						q.push(pp);//结构体压入队列
					}
				}
				if (now.n - 1 >= 0 && fl[now.n - 1]) {//原理同上
					fl[now.n - 1] = 0;
					struct nub pp;
					pp.n = now.n - 1;
					pp.step = now.step + 1;
					q.push(pp);
				}
				if (now.n * 2 <= 100000 && now.n >= 0) {//原理同上
					if (fl[now.n * 2]) {
						fl[now.n * 2] = 0;
						struct nub pp;
						pp.n = now.n * 2;
						pp.step = now.step + 1;
						q.push(pp);
					}
				}
			}
		}
	}
}

反思

开始甚至没想到bfs怎么写，算是对bfs有更深刻理解了

其次是标记数组为2*max，开始开了max光报错return time error

还有那个每次移动后都要判断在不在0~max间，一开始理解不利了是蒙上去的，后来想想如果不判断迟早会对max*2意外的数移动，那么判断的时候就会访问到max**2以外的部位导致数组越界报错return time error

总的来说就是个bfs，但这是第一次ac出来没有在二维数组里bfs的题，标记一下