C++迷宫问题的求解算法
本文实例为大家分享了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#include #definem4//行 #definen4//列 structxy { intx; inty; }; typedefstructstack { structxycoordinate; structstack*next; }stack; voidinit(stack*p) { p->next=NULL; } voidpush(stack*p,structxycdnt) { stack*temp=p; while(temp->next!=NULL) temp=temp->next; stack*newValue=(stack*)malloc(sizeof(structstack)*1); newValue->coordinate=cdnt; newValue->next=temp->next; temp->next=newValue; } voidpop(stack*p) { stack*tempp=p; stack*temp=p->next; while(temp->next!=NULL) temp=temp->next,tempp=tempp->next; tempp->next=NULL; free(temp); } voidbrowse(stack*p) { stack*temp=p->next; while(temp!=NULL) printf("(%d,%d)\n",temp->coordinate.y,temp->coordinate.x),temp=temp->next; } structxygetEnd(structstack*p) { stack*temp=p; while(temp->next!=NULL) temp=temp->next; returntemp->coordinate; } intgetSize(stack*p) { intsize=0; stack*temp=p->next; while(temp!=NULL) { size++; temp=temp->next; } returnsize; } intmain() { intpath[m+1][n+1]={0}; intcol=0,row=0; inti=0,j=0; inttemp_col=0,temp_row=0,t_col=0,t_row=0; intflag=0; structxyt_pair; //stackA,B; stack*Ahead=(stack*)malloc(sizeof(structstack)*1); stack*Bhead=(stack*)malloc(sizeof(structstack)*1); init(Ahead);init(Bhead); for(;i ::iteratoriter=B.end()-1; col=getEnd(Bhead).x+1;row=getEnd(Bhead).y;//回到上一次分叉处,搜索右侧路径 pop(Ahead); pop(Bhead); continue; } else return1; } //下面是,右边不是 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("Thereisnoway\n"); return0; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。