BFS（广度优先搜索）

BFS（Breadth first search）

适用范围：找到一条最快到达目标状态的路径。

算法过程：将当前搜索到的状态A的每一个子状态压入队列，检查队列是否为空，如果不为空，弹出队首元素，并且以这个状态为根节点继续进行广搜，直至整个队列为空。

伪代码：

初始化队列Q 
Q.push(head) 标记head为已访问 
while(!Q.empty())
{
	temp=Q.front();
	Q.pop();//取队首元素出队 
	if(temp==目标状态) 输出或操作; 
	if(temp不合法) continue; 
	if(temp合法) Q.push(temp+1);//表示所有temp的子节点 
	//所有与temp相邻且未被访问的点入队
	标记temp为已访问 	
} 

框架：

bool vis[maxn][maxn];//访问标记
int dir[4][2]={0,1,0,-1,1,0,-1,0};//方向向量

struct state//BFS队列中的状态数据结构
{
	int x,y;//坐标位置
	int step;//步数
};
state a[maxn];

bool check(state s)//约束条件检验
{
	if(!vis[s.x][s.y] && ...)//未访问且满足条件
	return 1;
	else//约束条件冲突
	return 0;
}

void bfs(state st)
{
	queue <state> q;//BFS 队列
	state now,next;//定义2 个状态，当前和下一个
	st.step=0;//计数器清零
	q.push(st);//入队
	vis[st.x][st.y]=1;//访问标记
	while(!q.empty())
	{
		now=q.front();//取队首元素进行扩展
		if(now==G)//出现目标态，此时为step 的最小值，可以退出即可
		{
			...... //做相关处理
			return;
		}
		for(int i=0;i<4;i++)
		{
			next.x=now.x+dir[i][0];//按照规则生成下一个状态
			next.y=now.y+dir[i][1];
			next.step=now.step+1;//计数器加1
			if(check(next))//如果状态满足约束条件则入队
			{
				q.push(next);
				vis[next.x][next.y]=1; //访问标记
			}
		}
		q.pop(); // 队首元素出队
	}
	 return;
}

int main()
{
......
 return 0;
}