//base.h
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//stack.h
#define STACK_INIT_SIZE 100 //存儲空間初始量
#define STACK_INCREMENT 10//存儲空間初始增量
typedef struct
{
int r;
int c;
}PostType;//坐標位置 迷宮的r行c列
typedef struct
{
int ord;//通道塊在路徑上的序號
PostType seat;//通道塊的當前坐標位置
int di;//通道塊指向下一通道塊的方向
}SElemType;//棧元素的類型
typedef struct
{
SElemType *base;//棧底指針
SElemType *top;//棧頂指針
int stacksize;//棧的最大容量
}Stack;//棧的類型
Status InitStack(Stack &S)//初始化棧
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存儲分配失敗;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack 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+STACK_INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;
}
*S.top++=e;
return OK;
}//Push
Status Pop(Stack &S,SElemType &e)
//刪除棧頂元素存入e
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S)
//銷毀棧
{
free(S.base);
S.top=S.base;
return OK;
}//DestroyStack
//maze.cpp
#define MAXLEN 20//迷宮包括外墻最大行列數目
typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType; //迷宮類型
Status InitMaze(MazeType &maze){
//初始化迷宮若成功返回TRUE,否則返回FALSE
int m,n,i,j,k=1;
printf("輸入迷口的行數和列數: ");
scanf("%d%d",&maze.r,&maze.c); //迷宮行和列數
for(i=0;i<=maze.c+1;i++){//迷宮行外墻
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}//for
for(i=0;i<=maze.r+1;i++){//迷宮列外墻
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';//初始化迷宮
printf("輸入障礙物%d的坐標(以坐標(0,0)結束輸入): ",k);
scanf("%d%d",&m,&n);//接收障礙的坐標
k++;
while(m!=0)
{
if(m>maze.r || n>maze.c)//越界
exit(ERROR);
maze.adr[m][n]='#';//迷宮障礙用'#'標記
printf("輸入障礙物%d的坐標(以坐標(0,0)結束輸入): ",k);
scanf("%d%d",&m,&n);
k++;
}
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]='*';//"*"表示可通
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
void PrintMaze(MazeType &maze)
//將最后標記好的迷宮輸出
{
int i,j;
printf("\n輸出迷宮的路徑:\n");
for(i=0;i<=maze.c+1;i++)
printf("%4d",i);//輸出列數
printf("\n");
for(i=0;i<=maze.r+1;i++)
{
printf("%d",i);//輸出行數
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);//輸出迷宮
printf("\n");
}
}//PrintMaze
Status MazePath(MazeType &maze,PostType start,PostType end)
//若迷宮從入口start到end的通道則求得一條存放在棧中
{
Stack S;//初始化棧
PostType curpos;
int curstep;
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)//到達出口返回TRUE
{
if(!DestroyStack(S))
exit(OVERFLOW);
else return TRUE;
}
else
{
curpos=NextPos(curpos,1);//下一位置是當前位置
curstep++;//探索下一步
}
}//if
else//當前位置不能通過
{
if(!StackEmpty(S))
{
Pop(S,e);//提取前一位置
while (e.di==4 && !StackEmpty(S))//4個方向都不能通過則留下記號@ 提取前一個位置進行判斷是否是能通過
{
MarkPrint(maze,e.seat);
Pop(S,e);
}
if(e.di<4)//換下一個方向探索 設定當前位置為該新方向上的鄰位
{
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);
}
}//if
}
}while(!StackEmpty(S));
if(!DestroyStack(S))
exit(ERROR);
else return FALSE;
}//MazePath
void main()
{
MazeType maze;
PostType start,end;
char c;
do
{
printf("----------找一條迷宮的路徑-------------\n");
if(!InitMaze(maze))
{
printf("\n 初始化迷宮失敗!!!");
exit(ERROR);
}
do
{
printf("\n請輸入入口的坐標:");
scanf("%d%d",&start.r,&start.c);//輸入入口坐標
if(start.r>maze.r || start.c>maze.c)
printf("\n輸入錯誤,請重新輸入入口的坐標!!\n");
continue;
}
while (start.r>maze.r || start.c>maze.c);
do
{
printf("\n請輸入出口的坐標:");//輸入出口的坐標
scanf("%d%d",&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c)
printf("\n輸入錯誤,請重新輸入出口坐標!!\n");
continue;
}
while (end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))
printf("\n不能找到一條路徑!!!\n");
else PrintMaze(maze);//輸出迷宮
printf("是否要繼續?(y/n):");
scanf("%s",&c);
}
while (c=='y' || c=='Y');
}//main