**Sample Input** 15 16 .**.***.***.*** ***.***..**.*.* .**.***.***.*** ***.***..**.*.* **.***.***.***. ***.***.......E .**.***.***.*.* ***..**...*...* .*....*.*...*.* ***.*.*.**.*..* ....*...**...** *.*.***..**.*.* .S*.***.***.*** ***.***..**.*.* .**.***.***.**. ***..**...*...* **Sample Output** The path is: (11,1) (10,1) (10,2) (10,3) (9,3) (8,3) (8,4) (8,5) (9,5) (10,5) (10,6) (10,7) (9,7) (8,7) (7,7) (6,7) (5,7) (5,8) (5,9) (5,10) (5,11) (5,12) (5,13) (5,14) 首先输入两个数代表迷宫的行数和列数,‘.’代表可以走的点，'*'代表墙，即不可以走的点。‘S’代表迷宫的入口，‘E’代表迷宫的出口。 由于广搜中，队列中的每一点被搜索到时都是在离起点最短的路径中被搜索到的，所以可以再建立一个以点的坐标为数据元素的二维数组，该二维数组每个数据元素对应迷宫中的每个点，其数据元素的值为该点在离起点最短的路径中的前一个点的坐标。这样迷宫的路径便不再由队列元素保存，所以出队并不影响路径的输出。 C++代码： ```cpp #include <iostream> #include <cstdio> #include <queue> using namespace std; struct box { int x,y; }; int main() { queue <box> qu; box q; box path[20][20];//用于记录路径 int output[400][2];//用于输出路径 char maze[20][20]; int m,n; int x0,y0;//记录起点位置 int di[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};//上下左右四个方向 bool flag; scanf("%d%d",&n,&m);//n是迷宫的行数，m是迷宫的列数 //读入迷宫 x0=y0=0; for(int i=0; i<m; ++i) { getchar(); for(int j=0; j<n; ++j) { scanf("%c",&maze[i][j]); if(maze[i][j]=='S') x0=i,y0=j; } } //起点进队 q.x=x0,q.y=y0; qu.push(q); maze[q.x][q.y]=-1;//防止再次回到起点 //开始搜索 flag=false; while(!qu.empty()&&!flag)//队列不为空并且没有找到目标时循环 { for(int i=0; i<4; ++i) { q.x=qu.front().x+di[i][0]; q.y=qu.front().y+di[i][1]; if(q.x<0||q.x>=m||q.y<0||q.y>=n)//坐标超出迷宫的范围 continue; if(maze[q.x][q.y]!='*'&&maze[q.x][q.y]!=-1)//该点可走 { qu.push(q); path[q.x][q.y]=qu.front();//记录迷宫中该点的前一点的位置 if(maze[q.x][q.y]=='E')//找到目标 { flag=true; break; } maze[q.x][q.y]=-1;//防止重复访问该点 } } qu.pop(); } //搜索结束，输出路径 if(flag==true)//迷宫有通路 { int step=0; while(q.x!=x0||q.y!=y0)//记录迷宫路径，以便正序输出 { output[step][0]=q.x; output[step][1]=q.y; int x=q.x; q.x=path[q.x][q.y].x; q.y=path[x][q.y].y; ++step; } printf("The path is:\n"); for(int i=step-1; i>=0; --i)//正序输出路径 printf("(%d,%d) ",output[i][0],output[i][1]); printf("\n"); } else//迷宫无通路 printf("The maze has no path!"); return 0; } ```