Question

数据结构中，求解迷宫问题的程序算法，，，

Answer 1

// test_03.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

struct PosType /* 迷宫坐标位置类型 */
{
int x; /* 行值 */
int y; /* 列值 */
};

int Maze[5][5] =
{
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};

#define MAXLENGTH 5

int curstep=1;
int a[MAXLENGTH];
int b[MAXLENGTH];

struct SElemType/* 栈的元素类型 */
{
int ord; /* 通道块在路径上的＂序号＂ */
PosType seat; /* 通道块在迷宫中的＂坐标位置＂ */
int di; /* 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) */
};

#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */

struct SqStack //SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}; /* 顺序栈 */

bool InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
{
exit(1); /* 存储分配失败 */
}
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return true;
}
bool Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
{
exit(1); /* 存储分配失败 */
}
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return true;
}

bool StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return true;
else
return false;
}

bool Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return false;
*e=*(--(*S).top);
return true;
}

bool Pass(PosType b)
{ /* 当迷宫m的b点的序号为1(可通过路径)，return true, 否则，return false */
if(Maze[b.x][b.y]==1)
return true;
else
return false;
}

void FootPrint(PosType a)
{ /* 使迷宫m的a点的序号变为足迹(curstep) */
Maze[a.x][a.y]=curstep;
}

PosType NextPos(PosType c,int di)
{ /* 根据当前位置及移动方向，返回下一位置 */
PosType direc[4]={{0,1},{1,0},{-1,0},{0,-1}};
/* 移动方向,依次为东南西北 */
c.x+=direc[di].x;
c.y+=direc[di].y;
return c;
}

void MarkPrint(PosType b)
{ /* 使迷宫m的b点的序号变为-1(不能通过的路径) */
Maze[b.x][b.y]=-1;
}

void Print(int x,int y)
{ /* 输出迷宫的解 */
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
cout<<"\t"<<Maze[i][j];
cout<<endl;
}
}

bool MazePath(PosType start,PosType end)
{
SqStack S;
SElemType e;
InitStack(&S);

a[0]=start.x;
b[0]=start.y;

PosType curpos=start;
do
{
if(Pass(curpos))
{ /* 当前位置可以通过，即是未曾走到过的通道块 */
FootPrint(curpos); /* 留下足迹 */

a[curstep]=curpos.x;
b[curstep]=curpos.y;

e.di=0;
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;

Push(&S,e);
// printf("PUSH1 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
if(curpos.x==end.x&&curpos.y==end.y)
return true;
curpos=NextPos(curpos,e.di);
curstep++;
}
else
{ /* 当前位置不能通过 */
if(!StackEmpty(S))
{
Pop(&S,&e); /* 退栈到前一位置 */
// printf("POP1 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
curstep--;
while((e.di==3) && (!StackEmpty(S)))
{
MarkPrint(e.seat);
Pop(&S,&e);
printf("POP2 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
curstep--;
}
if(e.di<3) /* 没到最后一个方向(北) */
{
e.di++;
// e.seat.x=curpos.x;
// e.seat.y=curpos.y;

Push(&S,e);
// printf("PUSH2 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord);
curpos=NextPos(e.seat,e.di);
curstep++;
}
}
}
}while(!StackEmpty(S));

return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
PosType begin,end;
begin.x = 1;
begin.y = 1;

end.x = 3;
end.y = 3;

if(MazePath(begin,end)) /* 求得一条通路 */
{
cout<<"此迷宫从入口到出口的一条路径如下:"<<endl;
Print(5,5); /* 输出此通路 */
for(int i=1;i<curstep;i++)
{
cout<<"("<<a[i]<<","<<b[i]<<")"<<"->";
}
cout<<"("<<a[curstep]<<","<<b[curstep]<<")"<<endl;
}
else
{
cout<<"此迷宫没有从入口到出口的路径"<<endl;
}

system("pause");
return 0;
}

Answer 2

深度优先遍历，等高线法

Answer 3

4个方向上递归遍历每个节点啊