基础BFS

广度优先算法(Breadth-First Search，BFS)是一种通过遍历进行搜索的方法，算法经过若干次循环，每次循环会访问所有能够访问的节点，为这些新节点打上标记，并且收集这些新节点所连接的所有节点信息，供下次循环来访问，直到访问到目标节点，算法结束。

数据结构

地图数组 Map

地图一般用数组来描述，地图的维数并不限制，其可以用来描述访问节点的方式、是否存在障碍物等。

//Map[5][9]
010101010
000010001
011110110
010000000
000111110

迷宫地图（入口左上角，出口右下角）的访问方式是上下左右前进1格，0表示通路，1表示障碍物。

标记数组 vis

标记数组可以避免算法访问已经访问过的节点，其一般和Map大小相同，区别是标记数组中1代表已访问过，0代表未访问过，当算法尝试访问一个节点时，会先判断标记数组是否为0，如果不为0，就不会访问该节点。

//vis[5][9]
100000000
000000000
000000000
000000000
000000000

算法初始化时，迷宫入口处是已访问过的，标记为1，其他地方均为0。

节点结构体 node

节点结构体可以记录每个节点的信息，例如：节点位置、第一次访问到该节点所走的路径、第一次访问到该节点所需的步数等、从哪个节点访问到此节点。
有时并不关注节点的具体信息，如判断迷宫是否有解时，如果访问到出口，便输出有解，所有节点均访问过还没访问到出口，便输出无解，不需要迷宫的走法，就没必要用结构体来描述节点。

//节点结构体
struct node{
    int x,y;    //节点位置
    int step;   //第一次访问到该节点所需步数
    string s;   //从第一个节点开始访问到该节点的过程，如"下左下下"
    node(){};   //构造函数，可以无参数生成节点
    node(int x,int y,int step,string s):x(x),y(y),step(step),s(s){};    //构造函数，可以带参数生成节点    
}

如果只写一种构造函数，就不能用另一种构造函数来生成节点
带参数的构造函数可以方便操作，例如：
假设存在一个集合A,A.insert()可以把节点加入到A集合
那么可以直接通过A.insert(node(1,1,2,”下右”))把节点位置为(1,1),访问到该节点需要2步，访问的路径为”下右”(从左上方入口向下1格再向右1格)的节点加入集合A

待访问节点队列 queue

广度优先搜索是个循环过程，每次循环均会产生下次循环所需访问的节点的集合，下次循环时拿出这些节点依次访问，这个过程可以通过队列来实现：
第一次循环把入口节点加入队列，
如果队列不为空，从队列头弹出一个节点访问并标记，然后把该节点能访问到的节点送入队列尾，循环这个过程。

//创建队列
queue<node> q;

//BFS算法所需了解的指令

//加入队列
//第一次搜索时，将左上角(0,0),访问所需步数为0，访问路径为空的入口节点加入队列
q.push(node(0,0,0,""))

//判断队列是否为空
while(!q.empty()){
    do someting;
}

//拿出队列头元素并弹出
node a=q.front();   //将头元素赋值给a
q.pop();    //弹出头元素

为方便而建立的数据

order字符串:方便路径字符串延伸

//order
string order="上下左右";

//目前节点为节点now，假设now.s="下右下"
node now=queue.front();

//访问now节点四周节点,相应的s="下右下"+order[i]
for(int i=0;i<4;++i)
string s=now.s+order[i];

dir数组:方便位置的计算 (direction)

//dir[][2]
dir[][2]={-1,0,1,0,0,-1,0,1};

//目前节点为节点now,假设now.x=now.y=0
node now;
now.x=0;now.y=0;

//访问now节点的下方节点时,相应的x=now.x+dir[i][0],y=now.y+dir[i][1]
for(int i=0;i<4;++i){
    x_next=now.x+dir[1][0];
    y_next=now.x+dir[1][1];
}

算法过程

定义数据
- 节点 struct node
- 地图 int Map[][]
- 标记 int vis[][]
- 队列 queue<node> q
- 方向字符串string order
- 方向数组int dir[][]
定义函数BFS
1. 将入口节点加入队列，并打上标记
2. 当队列不为空时，循环执行以下过程
  1. 取队列头元素节点，将其弹出，如果是目标节点，退出循环
  2. 遍历该节点所能访问的节点，如果遍历到的节点合法，生成节点的路径(由上一个节点的路径加访问方向产生)，步数(上一个节点的步数+1)等信息，并加入队列，打上标记。
    - 合法条件1:不越界，即节点位置不超出地图范围
    - 合法条件2:不为障碍物，即节点位置不为障碍物
    - 合法条件3:没有被访问过，即vis[节点位置]
    - 合法条件一般为这3条，但有可能有添加
主函数运行函数BFS()

例题《迷宫》蓝桥杯2019及代码

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。

请注意在字典序中 D<L<R<U。

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

运行限制
- 最大运行时间：1s
- 最大运行内存: 128M

代码

运行前需将迷宫复制到migong.txt中并将migong.txt放在代码cpp文件同目录下
运行前需将迷宫复制到migong.txt中并将migong.txt放在代码cpp文件同目录下
运行前需将迷宫复制到migong.txt中并将migong.txt放在代码cpp文件同目录下

取消注释可以看到BFS过程

#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y; 
	int step;
	string s;
	node(){};
	node(int x,int y,int step,string s):x(x),y(y),step(step),s(s){};
}; 
char Map[30][50]={0};
int vis[30][50]={0};
string order="DLRU";
int dir[][2]={1,0,0,-1,0,1,-1,0};
queue<node> q;

void bfs(){
	q.push(node(0,0,0,""));
	vis[0][0]=1;
	while(!q.empty()){
		node now=q.front();
		q.pop();
//		cout<<endl; 
//		cout<<"所在节点："<<now.x<<" "<<now.y<<endl;
//		cout<<"该节点路径："<<now.s<<endl;
		if(now.x==29&&now.y==49) {
//			cout<<endl;
//			cout<<"达到出口所需步数"<<now.step<<endl;
			cout<<"达到出口路径"<<now.s<<endl;
			break;
		}
		for(int i=0;i<4;i++){
			int x_next=now.x+dir[i][0];
			int y_next=now.y+dir[i][1];
			if(x_next>29||y_next>49||x_next<0||y_next<0) continue;
			if(Map[x_next][y_next]=='1') continue;
			if(vis[x_next][y_next]==1) continue;
			
			int step=now.step+1;
			string s=now.s+order[i];
			q.push(node(x_next,y_next,step,s));
//			cout<<x_next<<" "<<y_next<<"节点加入队列"<<endl; 
			vis[x_next][y_next]=1;
		}
	}
	
}
int main()
{
  freopen("migong.txt","r",stdin);
  for(int i=0;i<30;i++){
  	for(int j=0;j<50;j++){
  		cin>>Map[i][j];
	  }
  } 
  bfs();
  return 0;
}

解析

待补