小编给大家分享一下C++实现迷宫的具体代码,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
一、 实验目的:
(1) 熟练掌握链栈的基本操作及应用。
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。
二、实验内容:
【问题描述】
以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对信任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
【基本要求】
首先实现一个链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的迷宫,输出的一条通路为:(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),……。
【测试数据】/strong>
迷宫的测试数据如下:左上角(1,1)为入口,右下角(8,9)为出口。
1 2 3 4 5 6 7 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
【实现提示】
计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到则未能到达出口,则所设定的迷宫没有通睡。
可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(n,n)。为处理方便起见,可以迷宫的四周加一圈障碍。对于迷宫任一位置,均可约定有东、南、西、北四个方向可通。
【选作内容】
(1) 编写递归形式的算法,求得迷宫中所有可能的通路;
(2) 以方阵形式输出迷宫及其通路。
网友提供了一段解决算法:
#include<stdio.h> #include<stdlib.h> #define m 4//行 #define n 4//列 struct xy { int x; int y; }; typedef struct stack { struct xy coordinate; struct stack* next; }stack; void init(stack* p) { p->next = NULL; } void push(stack* p,struct xy cdnt) { stack* temp = p; while(temp->next != NULL) temp = temp->next; stack* newValue = (stack*)malloc(sizeof(struct stack)*1); newValue->coordinate = cdnt; newValue->next = temp->next; temp->next = newValue; } void pop(stack* p) { stack* tempp = p; stack* temp = p->next; while(temp->next != NULL) temp = temp->next,tempp = tempp->next; tempp->next = NULL; free(temp); } void browse(stack* p) { stack* temp = p->next; while(temp != NULL) printf("(%d,%d)\n",temp->coordinate.y,temp->coordinate.x),temp = temp->next; } struct xy getEnd(struct stack* p) { stack* temp = p; while(temp->next != NULL) temp = temp->next; return temp->coordinate; } int getSize(stack* p) { int size = 0; stack* temp = p->next; while(temp != NULL) { size++; temp = temp->next; } return size; } int main() { int path[m+1][n+1] = {0}; int col = 0,row = 0; int i = 0,j = 0; int temp_col = 0,temp_row = 0,t_col = 0,t_row = 0; int flag = 0; struct xy t_pair; //stack A,B; stack* Ahead = (stack*)malloc(sizeof(struct stack)*1); stack* Bhead = (stack*)malloc(sizeof(struct stack)*1); init(Ahead); init(Bhead); for(;i<m;i++) for(j=0;j<n;j++) { printf("input 0 or 1\n"); scanf("%d",&path[i][j]); } i = j = 0; if(path[0][0] == 0 || path[m-1][n-1] == 0) { printf("There is no way\n"); return 1; } while(1) { //检验是否已经到达末尾 if(col == n-1 && row == m-1 && path[row][col] == 1) { //到达尾端,意味着找到一条路 flag = 1; printf("Find a way,it's\n"); browse(Ahead); printf("(%d,%d)\n",m-1,n-1); if(getSize(Bhead) != 0) { temp_col = getEnd(Bhead).x; temp_row = getEnd(Bhead).y; while(1) if(getEnd(Ahead).x == temp_col && getEnd(Ahead).y == temp_row) break; else pop(Ahead); col = temp_col + 1; row = temp_row; pop(Bhead); } else return 1; } else//还没有到末尾的情况 { if(path[row + 1][col] == 1 && path[row][col + 1] == 1) { t_pair.x = col;t_pair.y = row; push(Ahead,t_pair); push(Bhead,t_pair); row++; continue; } //下面不是右边也不是 if(path[row + 1][col] == 0 && path[row][col + 1] == 0) { if(getSize(Bhead)) { //vector<struct xy>::iterator iter = B.end() - 1; col = getEnd(Bhead).x + 1;row = getEnd(Bhead).y;//回到上一次分叉处,搜索右侧路径 pop(Ahead); pop(Bhead); continue; } else return 1; } //下面是,右边不是 if(path[row + 1][col] == 1 && path[row][col + 1] == 0) { t_pair.x = col;t_pair.y = row; push(Ahead,t_pair); row++; continue; } //下面不是,右边是 if(path[row + 1][col] == 0 && path[row][col + 1] == 1) { t_pair.x = col;t_pair.y = row; push(Ahead,t_pair); col++; continue; } } } if(!flag) printf("There is no way\n"); return 0; }
以上是“C++实现迷宫的具体代码”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。