Question

急求用数据结构编写迷宫问题```

如提``

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;

//stack.h
#include "base.h"
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef struct{ //迷宫中r行c列的位置
int r;
int c;
}PostType;
typedef struct{
int ord; //当前位置在路径上的序号
PostType seat;//当前坐标
int di; //往下一坐标的方向
}SElemType; //栈元素类型
typedef struct
{
SElemType* base;//栈基址,构造前销毁后为空
SElemType* top;//栈顶
int stackSize; //栈容量
}Stack; //栈类型
Status InitStack(Stack &S){ //构造空栈s
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stackSize=INIT_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack S){
//若s为空返回TRUE,否则返回FALSE
if(S.top==S.base)
return TRUE;
return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >=S.stackSize){//栈满，加空间
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S){//销毁栈S,
free(S.base);
S.top=S.base;
return OK;
}//DestroyStack

//maze.cpp
#include "stack.h"
#define MAXLEN 10//迷宫包括外墙最大行列数目
typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType; //迷宫类型
Status InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
int m,n,i,j;
printf("Enter row and column numbers: ");
scanf("%d%d",&maze.r,&maze.c); //迷宫行和列数
for(i=0;i<=maze.c+1;i++){//迷宫行外墙
maze.adr[0][i]='1';
maze.adr[maze.r+1][i]='1';
}//for
for(i=0;i<=maze.r+1;i++){//迷宫列外墙
maze.adr[i][0]='1';
maze.adr[i][maze.c+1]='1';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';//初始化迷宫
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d%d",&m,&n);//接收障碍的坐标
while(m!=-1){
if(m>maze.r || n>maze.c)//越界
exit(ERROR);
maze.adr[m][n]='1';//迷宫障碍用'#'标记
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d%d",&m,&n);
}//while
return OK;
}//InitMaze
Status Pass(MazeType maze,PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
if(maze.adr[curpos.r][curpos.c]==' ')//可通
return TRUE;
else
return FALSE;
}//Pass
Status FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
maze.adr[curpos.r][curpos.c]='0';//"*"表示可通
return OK;
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
PostType cpos;
cpos=curpos;
switch(i){ //1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}
return cpos;
}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){
//曾走过但不是通路标记并返回OK
maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
return OK;
}//MarkPrint
Status MazePath(MazeType &maze,PostType start,PostType end){
//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
//并返回TRUE,否则返回FALSE
Stack S;
PostType curpos;
int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向
SElemType e;
InitStack(S);
curpos=start; //设置"当前位置"为"入口位置"
curstep=1; //探索第一步
do{
if(Pass(maze,curpos)){//当前位置可以通过,
//即是未曾走到过的通道
FootPrint(maze,curpos);//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e); //加入路径
if(curpos.r==end.r&& curpos.c==end.c)
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return TRUE; //到达出口
else{
curpos=NextPos(curpos,1);
//下一位置是当前位置的东邻
curstep++; //探索下一步
}//else
}//if
else{ //当前位置不通
if(!StackEmpty(S)){
Pop(S,e);
while(e.di==4
&& !StackEmpty(S)){
MarkPrint(maze,e.seat);
Pop(S,e);
//留下不能通过的标记,并退一步
}//while

if(e.di < 4){
e.di++;//换下一个方向探索
Push(S,e);
curpos=NextPos(e.seat,e.di);//设定当前位置是该
//新方向上的相邻
}//if
}//if
}//else
}while(!StackEmpty(S));
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return FALSE;
}//MazePath
void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出到终端(包括外墙)
int i,j;
printf("\nShow maze path(*---pathway):\n\n");
printf(" ");
for(i=0;i<=maze.r+1;i++)//打印列数名
printf("%4d",i);
printf("\n\n");
for(i=0;i<=maze.r+1;i++){
printf("%2d",i);//打印行名
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);//输出迷宫//当前位置的标记
printf("\n\n");
}
}//PrintMaze
void main(){ //主函数
MazeType maze;
PostType start,end;
char cmd;
do{
printf("-------FOUND A MAZEPATH--------\n");
if(!InitMaze(maze)){ //初始化并创建迷宫
printf("\nInitialization errors!!!\n");
exit(OVERFLOW); //初始化错误
}
do{ //输入迷宫入口坐标
printf("\nEnter entrance coordinate of the maze: ");
scanf("%d%d",&start.r,&start.c);
if(start.r>maze.r || start.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(start.r>maze.r || start.c>maze.c);
do{ //输入迷宫出口坐标
printf("\nEnter exit coordinate of the maze: ");
scanf("%d%d",&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))//迷宫求解
printf("\nNo path from entrance to exit!\n");
else
PrintMaze(maze);//打印路径
printf("\nContinue?(y/n): ");
scanf("%s",&cmd);
}while(cmd=='y' || cmd=='Y');
}//main