摘要
1.BFS的作用：遍历图找到与步长强相关的属性的最优解（也可以附带路径）
2.原理
起点入队，起点出队，从出队点开始下一步可以到达（符合条件）的所有点入队，队首再出队，从出队点开始下一步可以到达（符合条件）的所有点入队……。总之，步长为n的所有符合条件的点依次批量入队（n=0,1,2……），所以最先访问即步长最短，与步长相关的例如路径长度，消耗的时间最短，即最先访问即最优！
3.判断是否可以回头(不可随意重复访问标志的设立)
-
传统01：不可重复访问
-
如果图中存在能量补充点、时间重置点等等是可以回头的，可以回头的条件是剩余的能量或时间要大于上一次来到这个点时的剩余能量或时间
4.初始化
-
三个数组
- 地图数组（一般二维，可三维）：存放墙，可走点，能量补充点、时间充值点
- 路径变换数组（
s[走法种类数][维度]）：通常加法变换，也可以写成乘法矩阵变换 - 随意访问的数组（跟地图数组一个格式的结构体）：存标志量(传统01，上次到此点剩余能量时间)、路径量(这个点的上一个点的坐标）、其他想随时访问的属性
-
队列节点结构体
含x,y和仅终点访问的属性
3.实现方式（按常用程度排序）
- C自带队列
-
缺点：无法随意访问队列中任意节点，所以如果想要随时访问一个属性，此属性可以存在随意访问数组中
-
优点：书写简介方便
-
头文件：
#include <queue> -
定义代码：
queue<node> q; -
node:可以是结构体，一般含有x,y和仅终点访问的属性
-
通用代码：
1 |
void () |
-
自定义队列（需要知道程序需要的最大队列节点数）
自己写队列，不释放入队节点，只移动队首下标。所以可以随意访问队列中任意元素，在求解路径中只需要在队列的结构体中添加一个上一个节点的下标的属性就可以
-
优点：方便求解路径
-
队列元素结构：
struct point{int x,y,s;};s代表来源点的下标 -
队列结构：
struct p{point pp[1000];int t,w;};其中t表示队列的头，w表示队列的尾 -
push():
d.pp[d.w++]=a; -
!empty():
d.w!=d.t -
front()&pop():
a=d.pp[d.t++];
-
-
递归（没什么意义，还是用的队列）
就是原函数初始化在外面，while()循环体单独写成BFS函数，用!q.empty()判断是否运行此函数
dfs() 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void dfs()
{
a=q.front();
q.pop();
if(…………)//当前节点必须可以走下一步，比如能量没用完，时间还有
//有些时候规定到达终点时间为0不算，要>1
{
for(i=0;i<4;++i)//向题目中规定的方向走
{
b.x=a.x+s[i][0];//s数组存储变换矩阵,s[变幻种类][维度]
b.y=a.y+s[i][1];//当然也可以写成乘法那种矩阵
if()//判断是不是越界、和走到墙壁位置（如果是传统01标志现在就可以判断）
{
…………//计算b
if(…………){}//判断是不是能量补充点、时间重置点等等
else{}//如果不是要消耗能量和时间
if(能量和剩余时间<=上一次到达此点的能量和时间){…………;continue;}
//非01标志判断可不可以重复访问
if(){return;}//判断是不是终点，如果自定义队列求路径可以放在入队之后
…………//更新不可计算量（包括01标志）
q.push(b);
}
}
}
if(!q.empty())
dfs();
else
…………;//输出不能到达终点
}
queue<node> q;
node a,b;//a:起点、当前节点、出队点;b:下一节点
int main(){
…………//初始化a
…………/*初始化其他的不可计算量（不可通过上一节点计算的，比如上一次到达这个节点的剩余的时间或者能量）
用lasttime[][],memset(lastime,0,sizeof(lasttime))*/
…………//设置a点不可计算量
if(…………){…………;return;}//判断起点是不是最优解
q.push(a);
if(!q.empty())
dfs();
}4. 路径打印
因为一个点的来源只有一个，但一个点的去处可能有好多点，所以在存储路径的时候一般存储这个点的上一个点，但这样就出现了一个问题，打印路径的时候是倒着的，一般有两种方法解决这个问题，其实是一种
-
初始化
起点的前一个点的参数设置为-1，自带队列：
a[0][0].x=a[0][0].y=-1;自定义：a.s=-1; -
递归（隐式调用栈）
- c自带队列
1
2
3
4
5
6
7
8void print(int x,int y或者int n)//注意参数是-，null-0-0-0-
{
if(x==-1&&y==-1或者s==-1)
return ;
print(a[x][y].x,a[x][y].y或者p.a[n].s);
cout<<x<<y或者cout<<p.a[n].x<<p.a[n].y;
} -
显式用栈:没什么意义，写起来不方便
-
近期评论