POJ 3278 Catch That Cow

题目链接：POJ 3278 Catch That Cow

题目大意：
农夫知道一头牛的位置，想要抓住它。农夫和牛都在数轴上，农夫起始位于点(N)，牛位于点(K)。
农夫有两种移动方式：

1. 从(X)移动到(X-1)或(X+1)，每次移动花费一分钟；
2. 从(X)移动到(2*X)，每次移动花费一分钟。
   假设牛没有意识到农夫的行动，站在原地不动，最少要花多少时间才能抓住牛？

题解：
BFS遍历三种走法。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define io_speed_up ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
#define MAXN 100010
#define ms(a, b) memset(a, b, sizeof(a))

int n, m;
bool vis[2 * MAXN];
struct node {
	int loc, step;
};

int bfs() {
	int ans;
	vis[n] = true;
	queue <node> q;
	q.push(node{n, 0});
	while (!q.empty()) {
		node t = q.front();
		q.pop();
		if (t.loc == m) {
			ans = t.step;
			break;
		}
		for (int i = 1; i <= 3; ++i) {
			int loc;
			if (i == 1) loc = t.loc + 1;
			else if (i == 2) loc = t.loc - 1;
			else loc = t.loc * 2;
			if (loc > 0 && loc < 2 * m && !vis[loc]) {
				vis[loc] = true;
				q.push(node{loc, t.step + 1});
			}
		}
	}
	return ans;
}

int main() {
	io_speed_up;
	while (cin >> n >> m) {
		if (n > m) {
			cout << n - m << endl;
		} else {
			ms(vis, 0);
			cout << bfs() << endl;
		}
	}
	return 0;
}