POJ－3278 - Catch That Cow【BFS】

题意： John要去抓奶牛，奶牛不会移动，John移动的方式有三种：

1. 向前移动一步，耗时一分钟；
2. 向后移动一步，耗时一分钟；
3. 向前移动当前所处的位置的2倍，耗时一分钟；

题解：1. if(N >= k)，当John所处的位置大于奶牛的， John 只能向后一步一步移动，即耗时N - K ; 

    2. if(N < K），用BFS去解决; 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x7ffffff
using namespace std;
const int maxn = 1e5+1;
int N, K;
struct node
{int x, step;
};
int vis[maxn];
int bfs(int n, int k)
{queue<node> q;memset(vis, 0, sizeof(vis));node S;S.x = n, S.step = 0;vis[n] = true;q.push(S);while(!q.empty()){node now = q.front(), next;if(now.x == k){return now.step;}q.pop();for (int i = 0; i < 3; i++){if(i == 0) next.x = now.x + 1;else if(i == 1) next.x = now.x - 1;else next.x = now.x * 2;if(next.x < maxn && next.x >= 0 && !vis[next.x]){vis[next.x] = true;next.step = now.step + 1;q.push(next);}}}}
int main()
{scanf("%d%d", &N, &K);if(N >= K)printf("%d\n", N-K);elseprintf("%d\n",bfs(N, K));}
/*
4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
*/