©2020-2024 ioDraw All rights reserved
7-1 求解迷宫从入口到出口的一条最短路径 (15 分)
求解迷宫从入口到出口的一条最短路径。输入一个迷宫，求从入口通向出口的一条可行最短路径。为简化问题，迷宫用二维数组 int
maze[10][10]来存储障碍物的分布，假设迷宫的横向和纵向尺寸的大小是一样的，并由程序运行读入,
若读入迷宫大小的值是n（3<n<=10），则该迷宫横向或纵向尺寸都是n，规定迷宫最外面的一圈是障碍物，迷宫的入口是maze[1][1]，出口是maze[n-2][n-2],
若maze[i][j] = 1代表该位置是障碍物，若maze[i][j] = 0代表该位置是可以行走的空位（0<=i<=n-1,
0<=j<=n-1）。求从入口maze[1][1]到出口maze[n-2][n-2]可以走通的路径。要求迷宫中只允许在水平或上下四个方向的空位上行走，走过的位置不能重复走，规定必须按向右、向下、向左、向上的顺序向前搜索试探，输出先到达出口的最短路径。
如下这样一个迷宫：
对应的二维数组表示：
int maze[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,1,1},
{1,0,0,0,1,0,0,0,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,1,1,1,0,1,1,0,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
输入格式:
输入迷宫大小的整数n, 以及n行和n列的二维数组（数组元素1代表障碍物，0代表空位）。
输出格式:
输出按规定搜索试探顺序先到达出口的首条最短路径，依次输出从入口到出口可行最短路径每个位置的行列下标（i,j），每个位置间用“,”分隔。若没有通路，输出：NO。
输入样例1:
4 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1
输出样例1:
(1,1)(2,1)(2,2)
输入样例2:
10 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0
0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1
0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
输出样例2:
(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)(8,8)
#include<iostream> #include<queue> #include<cstring> using namespace std;
const int N=110; struct A { int x,y; }p[N][N];//存路径 int
dx[]={0,1,0,-1},dy[]={1,0,-1,0}; int pa[N][N],vis[N][N]; int n,l,flag=0; void
bfs(int r,int t)//宽度优先遍历找最短路径 { memset(vis,0,sizeof vis); queue<A>q;
q.push({r,t}); vis[r][t]=1; while(q.size()) { A ans=q.front(); q.pop();
if(ans.x==n-2&&ans.y==n-2)//到达终点时回溯 { flag=1; return; } for(int i=0;i<4;i++) {
int xx=ans.x+dx[i],yy=ans.y+dy[i];
if(xx>0&&xx<n&&yy>0&&yy<n&&!vis[xx][yy]&&!pa[xx][yy]) { vis[xx][yy]=1;
q.push({xx,yy}); p[xx][yy]=ans; } } } } void print(A it)//递归输出路径 {
if(it.x==1&&it.y==1) { printf("(%d,%d)",it.x,it.y); return; }
print(p[it.x][it.y]); printf("(%d,%d)",it.x,it.y); } int main() { cin>>n;
for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>pa[i][j]; bfs(1,1); if(!flag) {
cout<<"NO"<<endl; return 0; } A end={n-2,n-2}; print(end); return 0; }