迷宫的生成与路由(最好用C++版可以用的，一定追加50分)

来源：百度知道 编辑：UC知道 时间：2024/06/03 15:05:51
(1) 问题描述
设计算法生成一个N×M(N行M列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较(包括理论和实验)三种方法的时空复杂性。
(2) 课程设计目的
理解栈的应用，理解深(广)度优先思想，理解问题的理论和实验分析。
(3) 基本要求
① N和M是用户可配置的，缺省值为50和50。
② 迷宫的入口和出口分别在第0行和第N-1行上，随机选择。
③ 生成的迷宫要求是连通的。
④ 实现图形化界面(可用VC++，也可用C语言的图形库)。
⑤ 三种方法的试验比较应该在多个迷宫实例上(尤其可以选一些特定的迷宫)。
(4) 实现提示
多考虑栈上的运算。

#include<stdio.h>
#define r 64
#define m2 8
#define n2 10
int m=m2-2,n=n2-2;
typedef struct
{
int x,y; //行列坐标
int pre;
}sqtype;

sqtype sq[r];
struct moved
{
int x, y; //坐标增量，取值-1，0，1
}move[8];

int maze[m2][n2];

int PATH(int maze[][n2]) //找迷宫maze的路径
{
int i,j,k,v,front,rear,x,y;
int mark[m2][n2];
for(i=0;i<m2;i++)
for(j=0;j<n2;j++)
mark[i ][j]=0;
printf("Please Input move array\n");
for(i=0;i<8;i++)
{
scanf("%d,%d",&move[i ].x,&move[i ].y);
sq[1].x=1;
sq[1].y=1;
sq[1].pre=0;
front=1;
rear=1;
mark[1][1]=1; //标记入口以到达过
while(front<=rear)
{
x=sq[front].x;
y=sq[front].y; //(x,y)为出发点
for(v=0;v<8;v++) //搜索(x,y)的8个相邻(i,j)是否可以到达
{
i=x+move[v].x;
j=y+move[v].y;
if((maze[i ][j]==0