//
#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=0i<xi++)
{
for(j=0j<yj++)
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=1i<curstepi++)
{
cout<<"("<<a[i]<<","<<b[i]<<")"<<"->"
}
cout<<"("<<a[curstep]<<","<<b[curstep]<<")"<<endl
}
else
{
cout<<"此迷宫没有从入口到出口的路径"<<endl
}
system("pause")
return 0
}
#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=0i<=maze.c+1i++){//迷宫行外墙
maze.adr[0][i]='1'
maze.adr[maze.r+1][i]='1'
}//for
for(i=0i<=maze.r+1i++){//迷宫列外墙
maze.adr[i][0]='1'
maze.adr[i][maze.c+1]='1'
}
for(i=1i<=maze.ri++)
for(j=1j<=maze.cj++)
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+=1break
case 2 : cpos.r+=1break
case 3 : cpos.c-=1break
case 4 : cpos.r-=1break
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=0i<=maze.r+1i++)//打印列数名
printf("%4d",i)
printf("\n\n")
for(i=0i<=maze.r+1i++){
printf("%2d",i)//打印行名
for(j=0j<=maze.c+1j++)
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
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）