C++迷宫问题的求解算法

2023-07-28 09:20:06 78

本文实例为大家分享了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）。为处理方便起见，可以迷宫的四周加一圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。

【选作内容】

（１）编写递归形式的算法，求得迷宫中所有可能的通路；
（２）以方阵形式输出迷宫及其通路。

网友提供了一段解决算法：

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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

C++迷宫问题的求解算法

热门推荐

随机推荐