题目链接：http://poj.org/problem?id=3278
题意:农夫原始在N位置上，他的目的是要抓到在K位置上的牛。牛的位置是固定不变的，而农夫的移动是在一条水平线上进行的，移动方式有以下三种1、从当前位置往后移动一格；2、从当前位置往前移动一格；3、从当前位置pos瞬移到2*pos位置上。
刚开始我想利用DP来解决这道题，但是以失败告终，所以便参考了别人的解法，发现大多数人都是使用bfs来解决的。于是我改用bfs来处理。
代码实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=;//此处范围得准确，如果小了会Wrong int vis[maxn],step[maxn];
queue<int>que; int bfs(int N,int K)
{
int next,top;
que.push(N);//农夫所在初始点入队
vis[N]=true;//标记已被访问
step[N]=;//步数初始为0
while(!que.empty()){//队列非空时，执行循环
top=que.front();//取出队首
que.pop();//弹出队首
for(int i=;i<;i++){
if(i==) next=top-;
else if(i==) next=top+;
else next=top*;
if(next<||next>=maxn) continue;//如已出界，则排除该情况
if(!vis[next]){//如果改点还未被访问过
que.push(next);//入队
step[next]=step[top]+;//步数+1
vis[next]=true;//标记已被访问过
}
if(next==K) return step[next];//当遍历到结果，返回步数
}
}
}
int main()
{
int N,K;
while(~scanf("%d%d",&N,&K)){
memset(step,,sizeof(step));
memset(vis,false,sizeof(vis));
while(!que.empty()) que.pop();//注意调用前要先清空
if(N>=K) printf("%d\n",N-K);
else printf("%d\n",bfs(N,K));
}
return ;
}