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; }
 

技术
今日推荐
阅读数 170189
阅读数 23
阅读数 5
阅读数 0
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信