1075 - 迷宫问题
小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
Input
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
Output
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。
Examples
Input
1 5 5 S-### ----- ##--- E#--- ---##
Output
9
Solution C
#include<stdio.h> int main(void) { int k,x; scanf("%d",&x); for(k=1;k<=x;k++) {int i,j,m,n,w,i1,i2,i3,j1,j2,j3,f=0,r=1; char mg[105][105]; int zg[105][105],ins[105][105],tx[4]={0,1,0,-1},ty[4]={1,0,-1,0},q[10005]; scanf("%d%d",&n,&m); getchar(); for(i=0;i<n;i++) { for(j=0;j<m;j++) scanf("%c",&mg[i][j]); getchar();} for(i=0;i<n;i++) for(j=0;j<m;j++) { zg[i][j]=0; ins[i][j]=0; if(mg[i][j]=='S') {i1=i;j1=j;} } q[f]=i1*m+j1; zg[i1][j1]=1; while(f<r) {w=q[f]; i2=w/m;j2=w%m; f++; for(i=0;i<4;i++) { i3=i2+tx[i];j3=j2+ty[i]; if(i3>=0&&i3<n&&j3>=0&&j3<m&&(mg[i3][j3]!='#')&&(!zg[i3][j3])) {zg[i3][j3]=1; ins[i3][j3]=ins[i2][j2]+1; q[r]=i3*m+j3; r++; } } } for(i=0;i<n;i++) for(j=0;j<m;j++) if(mg[i][j]=='E') if(ins[i][j]!=0) printf("%d\n",ins[i][j]); else printf("-1\n"); } return 0; }
Solution C++
#include<iostream> #include<cstring> #include<queue> using namespace std; struct MAP { int x,y,step; }s,e,head,tail; char g[100][100]; int v[100][100],f[][2]={{-1,0},{0,1},{1,0},{0,-1}},n,m; int bfs() { memset(v,0,sizeof(v)); queue<struct MAP> q; q.push(s); s.step=0; v[s.x][s.y]=1; while(!q.empty()) { head=q.front(); q.pop(); for(int i=0;i<4;i++) { tail.x=head.x+f[i][0]; tail.y=head.y+f[i][1]; tail.step=head.step+1; if(!v[tail.x][tail.y]&&g[tail.x][tail.y]!='#'&&tail.x>=0&&tail.x<n&&tail.y>=0&&tail.y<m) { if(tail.x==e.x&&tail.y==e.y) return tail.step; v[tail.x][tail.y]=1; q.push(tail); } } } return -1; } int main() { int t,i,j; cin>>t; while(t--) { cin>>n>>m; for(i=0;i<n;i++) for(j=0;j<m;j++) { cin>>g[i][j]; if(g[i][j]=='S') { s.x=i; s.y=j; } else if(g[i][j]=='E') { e.x=i; e.y=j; } } cout<<bfs()<<endl; } return 0; }