poj3278：Catch That Cow

传送门

题目大意

在一条只能前进后退的一维路径上，给定起点n与重点k，只有三种移动方式：

1. 前进一步
2. 后退一步
3. 使坐标变为当前值的两倍

问走到终点最短需要几步。

思路

很经典的bfs板子题，直接bfs去枚举每一种走法。每次操作依次将三种移动方式计算所得的目标坐标放进队列，然后出队判断就行了。

代码

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int LIM = 100000;

queue<int> que;
bool vis[LIM + 10];
int steps[LIM + 10];

int bfs(int n, int k) {
	int now, next;
	que.push(n);
	vis[n] = true;
	steps[n] = 0;

	while(!que.empty()) {
		now = que.front();que.pop(); // 取队首
		//枚举操作
		for(int i = 0; i < 3; i++) {
			//分类讨论
			if(i == 0) {
				next = now - 1;
			} else if(i == 1) {
				next = now + 1;
			} else {
				next = now * 2;
			}

			//界外情况
			if(next < 0 || next >= LIM) continue;
			//没走过就可以走
			if(!vis[next]) {
				que.push(next);
				steps[next] = steps[now] + 1; // 步数转移
				vis[next] = true; // 标记当前位置
			}

			if(next == k) return steps[next]; // 到达k点，返回步数
		}
	}

	return 0;
}

int main() {
	int n, k;
	while(cin >> n >> k) {
		memset(vis, false, sizeof(vis));
		memset(steps, 0, sizeof(steps));
		while(!que.empty()) que.pop();

		if(n >= k) { // n点比k点远，只能一步一步倒回去
			printf("%d\n", n - k);
		} else {
			printf("%d\n", bfs(n, k));
		}
	}

	return 0;
}