赛前一天 常用算法总结

宽度优先搜索 BFS 广搜
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
/*
BFS 宽度优先搜索 一般我们称其为 广搜
BFS与DFS的不同之处在于搜索的顺序
BFS总是先搜索距离初始状态近的状态
对于同一个状态，BFS只经过一次，因此复杂度为O(状态数*转移的方式)
BFS运用到了队列
Step：
搜索时首先将初始状态添加到队列里
此后从队列的最前端不断取出状态
把从该状态可以转移到的状态中尚未访问的部分加入队列
如此往复知道队列为空
*/
/*
下面的 BFS 框架以2D坐标范围为例，来体现BFS算法的实现思想
*/
const int maxn=100;
bool vst[maxn][maxn];//访问标记
int dir[4][2]={0,1,0,-1,1,0,-1,0};
//BFS队列中的状态数据结构
struct State
{
int x,y;//坐标的位置
int Step_Counter;//搜索步数统计器
}
State a[maxn];
//约束条件检验
bool CheckEdge(State s)
{
if(!vst[s.x][s.y]&&...)
return true;
else
return false;
}
void bfs(State st)
{
queue<State> q;//BFS 队列
State now,next;//定义两个状态： 当前和下一个
st.Step_Counter=0;//计数器清零
q.push(st);//入队
vst[st.x][st.y]=1;//标记访问
while(!q.empty())//队列不为空时
{
now=q.front();//取队首元素进行扩展
if(now==Goal)//出现目标，此时为Step_Counter的最小值，退出即可
{
/*
Code... //相关操作
*/
return ;
}
for(int i=0;i<4;i++)
{
next.x=now.x+dir[i][0];//按照规则生成下一个状态
next.y=now.y+dir[i][1];
next.Step_Counter=now.Step_Counter+1;//计数器加 1
if(CheckState(next))
{
q.push(next);
vst[next.x][next.y]=1;//????
}
}
q.pop();//队首出队
}
return ;
}
int main()
{
/*
Code...
bfs....
*/
return 0;
}