Catch The Caw——（广度优先搜索的应用，队列）

Catch The Caw——（广度优先搜索的应用，队列）

抓住那头牛(POJ3278)
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上
，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)
。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要
花多少时间才能抓住牛？

广搜算法
广度优先搜索算法如下：（用QUEUE）
(1) 把初始节点S0放入Open表中；
(2) 如果Open表为空，则问题无解，失败
退出；
(3) 把Open表的第一个节点取出放入
Closed表，并记该节点为n；
(4) 考察节点n是否为目标节点。若是，
则得到问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，将其不在Closed表和
Open表中的子节点(判重） 放入Open表的尾部
， 并为每一个子节点设置指向父节点的指针(
或记录节点的层次） ，然后转第(2)步。

#include<iostream>
#include<queue>
#include<string>
#include<malloc.h>
using namespace std;#define MAX_SIZE 10000//查询最大的范围
int visited[MAX_SIZE];//标记那个位置是否已经走过了
struct Node
{int x;//位置int step;//走到这个位置所需要几步Node(int a=0,int b=0):x(a),step(b){}
};queue<Node> open;//广度优先搜索，类似于一层一层的去遍历查找
int main()
{cout<<"输入农夫的位置N(0<=N<=100000)："<<endl;int N;cin>>N;cout<<"输入牛的位置K(0<=K<=100000)："<<endl;int K;cin>>K;memset(visited,0,sizeof(visited));Node N_start(N,0);//人位置.Node K_caw(K,0);//牛位置.int min_step;//最终的最少的步骤.Node N_step(0,0);//中间存储变量.N_step=N_start;open.push(N_step);//将开始的位置输入到队列中visited[N_start.x]=1;while(!pty()){N_step=open.front();//取出队列头的元素，进行判断open.pop();if(N_step.x==K)//若是找到了则跳出循环{min_step=N_step.step;break;}else{//加1的位置元素if((N_step.x+1<MAX_SIZE)&&visited[N_step.x+1]==0){visited[N_step.x+1]=1;open.push(Node(N_step.x+1,N_step.step+1));}if(N_step.x-1>=0&&visited[N_step.x-1]==0)//减1的位置元素{visited[N_step.x-1]=1;open.push(Node(N_step.x-1,N_step.step+1));}if(N_step.x*2<MAX_SIZE&&visited[N_step.x*2]==0)//*2的位置的元素{visited[N_step.x*2];open.push(Node(N_step.x*2,N_step.step+1));}}}cout<<min_step<<endl;system("pause");return 1;
}

转载于:.html