迷宫最短路径——广度搜索

给出地图n*m，求出从起点到重点的最短路径长度
题目假定，一定可以到达
S是起点 ，G是终点，#是不通路，.是通路
【样例】
【输入】
10 10
#S######.#
…#…#
.#.##.##.#
.#…
##.##.####
…#…#
.#######.#
…#…
.####.###.
…#…G#
【输出】
22

用广度搜索，具体分析讲解看代码…
（注释挺详细的~有问题可私聊or评论留言）

#include
#include
#define N 100+5
#define INFINITY 9999999
using namespace std;
typedef pair P;//typedef重命名 pair->P
int n,m;
char a[N][N];//地图

P s;//起点坐标
P g;//终点坐标

int D[N][N];//距离数组

int dx[]= {0,0,1,-1};//控制上下左右移动的数组
int dy[]= {1,-1,0,0};

int bfs() {//广度搜索
	queue
 Q;
	Q.push(s);
	while(!Q.empty()) {
		P temp=Q.front() ;//取坐标
		Q.pop() ;
		for(int i=0; i<4; i++) {
			P curr;
			curr.first =temp.first +dx[i];//移动位置 
			curr.second =temp.second +dy[i];
			if(a[curr.first ][curr.second ]!='#') {//是通路 
				if(curr.first >=0 and  curr.first =0 and  curr.second >n>>m;
	for(int i=0; i>a[i][j];//输入地图
			D[i][j]=INFINITY;//距离数组初始化
			if(a[i][j]=='S') {//找寻起点坐标
				s.first =i;//记录起点坐标
				s.second =j;
				D[i][j]=0;//起点初始化
			}
			if(a[i][j]=='G') { //找寻终点坐标
				g.first =i;//记录终点坐标
				g.second =j;
			}
		}
	}
	solve();
}

1. typedef 重命名

2. 如果是上下左右移动，建立数组：

   如果是四周八个方向移动，用双重for循环

3. 因为是广度搜索，所以一旦到达了终点，则一定是最短距离，即可return；

4. pair<>;用first second 调用

5. 时间复杂度是O（N*M）

6. 这里的距离数组记录距离的同时也起到了标记访问的作用