小明置身于一个迷宫,请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入包含多组测试数据。输入的第一行是一个整数T,表示有T组测试数据。
每组输入的第一行是两个整数N和M(1<=N,M<=100)。
接下来N行,每行输入M个字符,每个字符表示迷宫中的一个小方格。
字符的含义如下:
‘S’:起点
‘E’:终点
‘-’:空地,可以通过
‘#’:障碍,无法通过
输入数据保证有且仅有一个起点和终点。
对于每组输入,输出从起点到终点的最短路程,如果不存在从起点到终点的路,则输出-1。
1
5 5
S-###
-----
##---
E#---
---##
9
#include<stdio.h> #include<iostream> #include<queue> #define maxn 105 using namespace std; int t; int m,n; int sx,sy;//起点 int ex,ey;//终点 char map[maxn][maxn]; //存图 int vis[maxn][maxn];//判断是否遍历过 int dist[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//四个方向 int ans; struct node { int x; int y; int step; }; bool check(int x,int y) { if(x>=0&&x<m&&y>=0&&y<n&&map[x][y]!='#'&&vis[x][y]==0) return true; return false; } void bfs() { queue<node> q; node a; node next; a.x=sx; a.y=sy; a.step=0; vis[a.x][a.y]=1; q.push(a); //始点入列 while(!q.empty())//队列非空 { a=q.front();//取首元素 q.pop();<span style="font-family:'Lucida Console';"> //取出后删除首元素</span> for(int i=0;i<4;i++)//向四个方向遍历 { next=a; next.x+=dist[i][0]; next.y+=dist[i][1]; next.step=a.step+1; if(next.x==ex&next.y==ey)<span style="font-family:'Lucida Console';">//判断是否是终点</span> { ans=next.step; return ; } if(check(next.x,next.y))//遍历标记,且入列 { vis[next.x][next.y]=1; q.push(next); } } } ans=-1;//<span style="font-family:'Lucida Console';">死路</span> } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&m,&n); for(int i=0;i<m;i++) { scanf("%s",&map[i]); for(int j=0;j<n;j++) { if(map[i][j]=='S')//得起点坐标 { sx=i; sy=j; } if(map[i][j]=='E')//得终点坐标 { ex=i; ey=j; } } } bfs(); printf("%d\n",ans); } return 0; }
原文:http://blog.csdn.net/u013067957/article/details/38273025