bfs广度优先搜索

最近做了一些搜索题，突然，发现，原来是有套路这种东西存在的。总结了一些比较基础的bfs代码。该代码是poj3278农夫追牛问题的AC代码：

代码如下：

主要看注释

#include <iostream> #include<queue> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; #define N 10000000//迷宫的规模 type start,aim;//type为某种数据类型 //start初始位置，aim目标位置 struct node{ int x; int step; }; //记录两种状态 //1.记录该步的状态 //2.步数 bool vis[N]; //标记该种状态是否被走过 queue<node> q; //广搜队列 void bfs() { while(!q.empty()) { if(q.front().x==aim) { return; } node tmp; //tmp用于暂时储存状态 int X=q.front().x; //一维只有X //多维要从多重维度记录 int Step=q.front().step; q.pop(); //进行减一的操作 //广度试探 if(X>=1&&!vis[X-1]) //要保证减1后有意义,所以要X >= 1 //其中之一的试探条件 { tmp.x=X-1;//进行操作 //到达新的状态 tmp.step=Step+1; vis[X-1]=1; //记录已经到达过的位置 //记录该状态已经试探过了 q.push(tmp); } //已经到达的位置不能重复到达 //进行加一的操作 if(X<aim&&!vis[X+1]) //总的来说试探条件有三个 //1.在边界之内 //2.还未走过 //3.该处没有”墙“ { tmp.x=X+1; tmp.step=Step+1; vis[X+1]=1; q.push(tmp); } //进行乘两倍的操作 if(X<aim&&!vis[2*X]) { tmp.x=2*X; tmp.step=Step+1; vis[2*X]=1; q.push(tmp); } } } int main() { while(cin>>start>>aim)//初始化迷宫 { memset(vis,0,sizeof(vis)); //初始化记录状态的数组 while(!q.empty())q.pop(); //确保在进行操作之前队列为空 node ST; ST.x=start; ST.step=0; q.push(ST); //将根节点进队 //同时开始广度优先搜索 bfs(); //可能在此处会有一个较为复杂的输出函数 cout<<q.front().step<<endl; } return 0; } //可以证明此处进队的可以是整个对象