3048: 抓住那头牛

解题思路: BFS： 三种移动方向 + 1， - 1， 2 * x

注意事项:

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int g[N],n,k;
bool v[N];
int que[2*N], tt = -1, ff = 0; 
void bfs(int x){
	v[x] = true;
	que[++tt] = x;
	while(ff <= tt){
		int cx = que[ff++];
		for(int i = 0; i < 3; i ++){
			int nx;
			if(i == 0) nx = cx + 1;
			else if(i == 1) nx = cx - 1;
			else nx = 2 * cx; 
			if(nx >= 0 && nx <= N && !v[nx]){
				v[nx] = true;
				if(g[nx] > g[cx] + 1) g[nx] = g[cx] + 1;
				que[++tt] = nx;
			} 
		}		
	}
}
int main()
{
	cin >> n >> k;
	memset(g,0x3f, sizeof(g));
	g[n] = 0;
	bfs(n);
	cout << g[k];
	return 0;
}