广度优先搜索（BFS）C++

广度优先搜索（BFS）

宽度优先搜索（BFS，Breadth-First Search）也是搜索的手段之一。宽度优先搜索是先搜索距离初始状态近的状态。也就是说，它是按照开始状态→只需1次转移就可以到达的所有状态→只需2次转移就可以到达的所有状态→……这样的顺序进行搜索

宽度优先搜索利用了队列进行计算，队列（Queue）支持push和pop两个操作，数据元素先进先出。其头文件为：#include <queue>

例题：迷宫的最短路径

题目描述

给定一个大小为 N×M 的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。

限制条件
N, M ≤ 100

样例输入

N=10, M=10（迷宫如下图所示。’#’，’.’，‘S’，'G’分别表示墙壁、通道、起点和终点）
#S######.#
…#…#
.#.##.##.#
.#…
##.##.####
…#…#
.#######.#
…#…
.####.###.
…#…G#

样例输出

22

题目分析

宽度优先搜索按照距开始状态由近及远的顺序进行搜索，因此可以很容易地用来求最短路径、最少操作之类问题的答案。这个问题中，状态仅仅是目前所在位置的坐标，因此可以构造成pair或者编码成int来表达状态。

宽度优先搜索中，只要将已经访问过的状态用标记管理起来，就可以很好地做到由近及远的搜索。这个问题中，由于要求最短距离，不妨用d[N][M]数组把最短距离保存起来。初始时用充分大的常数INF来初始化它，这样尚未到达的位置就是INF，也就同时起到了标记的作用。

虽然到达终点时就会停止搜索，可如果继续下去直到队列为空的话，就可以计算出到各个位置的最短距离。此外，如果搜索到最后，d依然为INF的话，便可得知这个位置就是无法从起点到达的位置。

因为要向4个不同方向移动，用dx[4]和dy[4]两个数组来表示四个方向向量。这样通过一个循环就可以实现四方向移动的遍历。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std; 

const int INF = 100000000;
const int MAX_N = 10001;

//使用pair表示状态时，使用typedef会更方便一些 
typedef pair<int, int> P;

char maze[MAX_N][MAX_N+1];	//表示迷宫的字符串数组 
int N, M;
int sx, sy;					//起点坐标 
int gx, gy;					//终点坐标 

int d[MAX_N][MAX_N];		//到各个位置的最短距离数组 

//4个方向移动的向量 
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

//求从(sx,sy)到(gx,gy)的最短距离 
//如果无法到达，则是INF 
int bfs(){
	queue<P> que;
	
	//把所有的位置都初始化为INF 
	for(int i=0; i<N; i++)
		for(int j=0; j<M; j++){
			d[i][j] = INF;
		}
	
	//将起点加入到队列，并把这一地点的距离设置为0 
	que.push(P(sx,sy));
	d[sx][sy] = 0;
	
	//不断循环直到队列的长度为0 
	while(que.size()){
		
		//从队列的最前端取出元素 
		P p = que.front(); 
		que.pop();
		
		//判断取出的元素是否为终点，若是终点，则结束搜索 
		if(p.first == gx && p.second == gy)
			break;
		
		//四个方向的循环 
		for(int i=0; i<4; i++){
			//移动之后的位置记为(nx,ny) 
			int nx = p.first + dx[i], ny = p.second + dy[i];
			
			//判断 是否可以移动以及是否已经访问过（d[nx][ny]!=INF即已经访问过） 
			if(0<=nx && nx < N && 0<=ny && ny < M && maze[nx][ny]!='#' && d[nx][ny]==INF){
				//可以移动的话，则加入到队列，并且到该位置的距离确定为到p的距离+1 
				que.push(P(nx,ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
		
	}
	
	return d[gx][gy];
}

int main(){
	cin >> N >> M;
	
	for(int i=0; i<N; i++)
		for(int j=0; j<M; j++)
			cin >> maze[i][j];
	
	//确定起始位置坐标 
	for(int i=0; i<N; i++)
		for(int j=0; j<M; j++){
			if(maze[i][j] == 'S'){
				sx = i;
				sy = j;
			}
			else if(maze[i][j] == 'G'){
				gx = i;
				gy = j;
			}
		}
	
			
	int res = bfs();
	cout << res;
	return 0;
}