问题 H: 迷宫问题

题目描述

定义一个二维数组：  int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,}; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出

左上角到右下角的最短路径，格式如样例所示

样例输入复制

0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

样例输出复制

(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4) #include<iostream> #include<cstring> #include <queue>using namespace std;const int maxn = 5+5; int map[maxn][maxn]; bool visit[maxn][maxn]; int dx[4]={1,0,0,-1}; int dy[4]={0,-1,1,0}; int n=5;struct Point{int x;int y; };Point book[maxn][maxn]; void BFS() {queue<Point> q{};q.push({0,0});while(!q.empty()){Point p = q.front();q.pop();if(p.x==4&&p.y==4){return;}for(int i=0;i<4;i++){int nx = p.x+dx[i];int ny = p.y+dy[i];if(nx<0||nx>=n||ny>=n||ny<0||visit[nx][ny]||map[nx][ny]==1)continue;book[nx][ny]=p;q.push({nx,ny});visit[nx][ny]= true;}} } void DFSprint(int i,int j) {if(i==0&&j==0){printf("(%d,%d)\n",i,j);return;}DFSprint(book[i][j].x,book[i][j].y);printf("(%d,%d)\n",i,j); } int main() {memset(visit,false, sizeof(visit));memset(map,1,sizeof(map));for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>map[i][j];}}BFS();DFSprint(4,4);return 0; }

总结

以上是生活随笔为你收集整理的问题 H: 迷宫问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。