标准模板——bfs迷宫问题

解题思路:

bfs刚好满足于queue的逻辑，
运用queue对每次新的坐标入队

具体代码如下

参考代码:

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

const int MAXC = 1000;

int r,c;
char mapp[MAXC][MAXC];
int vis[MAXC][MAXC];
int start_x,start_y;
int end_x,end_y;

int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void bfs(){
        //这是一个队列（queue）的定义，其中每个元素是一个pair类型，pair中包含两个int类型的元素。
	queue<pair<int , int >> q;
	
	//其中q是一个queue类型的变量，make_pair(start_x, start_y)是一个pair类型的变量，
	//表示一个二元组，将start_x和start_y打包在一起。这行代码的作用是将这个二元组压入队列q中。
	q.push(make_pair(start_x,start_y));
	vis[start_x][start_y] = 1;
	//因为考虑到“计算步数要包括起点和终点。”所以step初始值给1表示起点步数
	int step = 1;
	while(!q.empty()){
		int len = q.size();
		while(len--){
			int x = q.front().first;    //取出的第一个数值被赋值给变量x
			int y = q.front().second;    //第二个数值被赋值给变量y
			//这段代码是从队列（queue）中取出第一个元素，并将其弹出队列。
			q.pop();
			
			if(x == end_x && y == end_y){
			//判断该坐标(x,y)是否到达终点(end_x,end_y)
				cout<<step;
				return;
			}
			for(int i=0;i<4;i++){
			//将坐标(x,y)向四个方向分别偏移一定量，得到四个新的坐标(dx,dy)。
				int dx = x + d[i][0]; 
				int dy = y + d[i][1];
				
				if(dx>0 && dx<=r && dy>0 && dy<=c && !vis[dx][dy] && mapp[dx][dy]=='.' ){
				//枚举4个方向，合适的就入队
					q.push(make_pair(dx,dy));
					vis[dx][dy] = 1;
				}
			}
		}
		step++;
	}
	cout<<"not answer";    //没答案输出-1。因题目所给案例都可以走出迷宫，所以可以计较
}

int main(void){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>mapp[i][j];
		}
	}
	start_x = 1;start_y = 1;    //对起点进行标记，坐标赋值给start_x,start_y;
	end_x = r; end_y = c;    //对终点坐标进行标记
	bfs();   
	
	return 0;
}