迷宫入门问题

原题

题目描述

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

输入

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

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-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,int> P; //坐标 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<P> qu; 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; }