迷宫问题

原题

题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。

输入

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1
5 5
s-###
-----
##---
E#---
---##

样例输出

9

解决代码

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include <algorithm>
using namespace std;
int de[100][100];//计步数组  记录走到这个位置所需的步数 不能走到的位置标记为-1 
char map[100][100];  //用于存放迷宫地图 
typedef pair<int,intP;  //坐标
int to[2][4]={1,-1,0,0,0,0,1,-1};  //在当前坐标下能走的四个方向
int sx,ex,sy,ey;  //(sx,sy)为起点坐标  （ex,ey）为终点坐标
int x,y,nx,ny; //(x,y)为函数中当前位置坐标   （nx,ny)为接下来能到达的坐标 
int r,l;  //r为行数 l为列数 
int bfs()
{
	memset(de,-1,sizeof(de));
	queue<Pqu;
	qu.push(P(sx,sy));   //将起点坐标放入队头 
	de[sx][sy]=0;
	while(!qu.empty()) 
	{
		P p=qu.front();   //取出队头坐标 
		qu.pop() ;//删除对头及走过的坐标 
		x=p.first,y=p.second; 
		if(x==ex&&y==ey) break; //到达终点 跳出循环		
	 	for(int i=0;i<4;i++)
		{
			nx=x+to[0][i];//开始向四个方向移动 
			ny=y+to[1][i];			
				if(nx>=0&&nx<r&&ny>=0&&ny<l&&map[nx][ny]!='#'&&de[nx][ny]==-1)
	 //判断是否越界 以及是否能走  排除走过的路 
	 {
	 	 qu.push(P(nx,ny));  //将能走的坐标放入队列 之后依次删除 
						 de[nx][ny]=de[x][y]+1;  //步数加一 
					  } 				  
			}
	}
	if(de[ex][ey]==-1)  return -1;  //终点的记步数组为-1 及不能到达终点 
	else return de[ex][ey]; 
} 
int main()
{
	int n,i,j;
	while(cin>>n){
		while(n--){
			cin>>r>>l;
			for(i=0;i<r;i++){
				for(j=0;j<l;j++){ 
				cin>>map[i][j];
				if(map[i][j]=='S') //记录起点坐标 
				 {
					sx=i,sy=j;
				 } 
				 else if(map[i][j]=='E')  //记录终点坐标 
				 {
				 	ex=i,ey=j;
				 }
				}
			}
			cout<<bfs()<<endl;
		}
	}
	return 0;
}