//
#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
*迷宫源程序*/#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define N 20/*迷宫的大小，可改变*/
int oldmap[N][N]/*递归用的数组,用全局变量节约时间*/
int yes=0/*yes是判断是否找到路的标志,1找到，0没找到*/
int way[100][2],wayn=0/*way数组是显示路线用的,wayn是统计走了几个格子*/
void Init(void)/*图形初始化*/
void Close(void)/*图形关闭*/
void DrawPeople(int *x,int *y,int n)/*画人工探索物图*/
void PeopleFind(int (*x)[N])/*人工探索*/
void WayCopy(int (*x)[N],int (*y)[N])/*为了8个方向的递归，把旧迷宫图拷贝给新数组*/
int FindWay(int (*x)[N],int i,int j)/*自动探索函数*/
void MapRand(int (*x)[N])/*随机生成迷宫函数*/
void PrMap(int (*x)[N])/*输出迷宫图函数*/
void Result(void)/*输出结果处理*/
void Find(void)/*成功处理*/
void NotFind(void)/*失败处理*/
void main(void)/*主函数*/
{
int map[N][N]/*迷宫数组*/
char ch
clrscr()
printf("\n Please select hand(1) else auto\n")/*选择探索方式*/
scanf("%c",&ch)
Init()/*初始化*/
MapRand(map)/*生成迷宫*/
PrMap(map)/*显示迷宫图*/
if(ch=='1')
PeopleFind(map)/*人工探索*/
else
FindWay(map,1,1)/*系统自动从下标1,1的地方开始探索*/
Result()/*输出结果*/
Close()
}
void Init(void)/*图形初始化*/
{
int gd=DETECT,gm
initgraph(&gd,&gm,"c:\\tc")
}
void DrawPeople(int *x,int *y,int n)/*画人工控制图*/
{/*如果将以下两句注释掉，则显示人工走过的路径，*/
setfillstyle(SOLID_FILL,WHITE)/*设置白色实体填充样式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6)
/*恢复原通路*/
switch(n)/*判断x,y的变化，8个方向的变化*/
{
case 1: (*x)--break/*上*/
case 2: (*x)--(*y)++break /*右上*/
case 3: (*y)++break/*右*/
case 4: (*x)++(*y)++break/*右下*/
case 5: (*x)++break/*下*/
case 6: (*x)++(*y)--break/*左下*/
case 7: (*y)--break/*左*/
case 8: (*x)--(*y)--break/*左上*/
}
setfillstyle(SOLID_FILL,RED)/*新位置显示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6)
}
void PeopleFind(int (*map)[N])/*人工手动查找*/
{
int x,y
char c=0/*接收按键的变量*/
x=y=1/*人工查找的初始位置*/
setcolor(11)
line(500,200,550,200)
outtextxy(570,197,"d")
line(500,200,450,200)
outtextxy(430,197,"a")
line(500,200,500,150)
outtextxy(497,130,"w")
line(500,200,500,250)
outtextxy(497,270,"x")
line(500,200,450,150)
outtextxy(445,130,"q")
line(500,200,550,150)
outtextxy(550,130,"e")
line(500,200,450,250)
outtextxy(445,270,"z")
line(500,200,550,250)
outtextxy(550,270,"c")/*以上是画8个方向的控制介绍*/
setcolor(YELLOW)
outtextxy(420,290,"Press 'Enter' to end")/*压回车键结束*/
setfillstyle(SOLID_FILL,RED)
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6)/*入口位置显示*/
while(c!=13)/*如果按下的不是回车键*/
{
c=getch()/*接收字符后开始各个方向的探索*/
if(c=='w'&&map[x-1][y]!=1)
DrawPeople(&x,&y,1)/*上*/
else
if(c=='e'&&map[x-1][y+1]!=1)
DrawPeople(&x,&y,2)/*右上*/
else
if(c=='d'&&map[x][y+1]!=1)
DrawPeople(&x,&y,3)/*右*/
else
if(c=='c'&&map[x+1][y+1]!=1)
DrawPeople(&x,&y,4)/*右下*/
else
if(c=='x'&&map[x+1][y]!=1)
DrawPeople(&x,&y,5)/*下*/
else
if(c=='z'&&map[x+1][y-1]!=1)
DrawPeople(&x,&y,6)/*左下*/
else
if(c=='a'&&map[x][y-1]!=1)
DrawPeople(&x,&y,7)/*左*/
else if(c=='q'&&map[x-1][y-1]!=1)
DrawPeople(&x,&y,8)/*左上*/
}
setfillstyle(SOLID_FILL,WHITE)/*消去红色探索物，恢复原迷宫图*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6)
if(x==N-2&&y==N-2)/*人工控制找成功的话*/
yes=1/*如果成功标志为1*/
}
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */
{
int i,j
for(i=0i<Ni++)
for(j=0j<Nj++)
oldmap[i][j]=map[i][j]
}
int FindWay(int (*map)[N],int i,int j)/*递归找路*/
{
if(i==N-2&&j==N-2)/*走到出口*/
{
yes=1/*标志为1,表示成功*/
return
}
map[i][j]=1/*走过的地方变为1*/
WayCopy(oldmap,map)/*拷贝迷宫图*/
if(oldmap[i+1][j+1]==0&&!yes)/*判断右下方是否可走*/
{
FindWay(oldmap,i+1,j+1)
if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
WayCopy(oldmap,map)
if(oldmap[i+1][j]==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/
{
FindWay(oldmap,i+1,j)
if(yes)
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
WayCopy(oldmap,map)
if(oldmap[i][j+1]==0&&!yes)/*判断右方是否可以走*/
{
FindWay(oldmap,i,j+1)
if(yes)
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
WayCopy(oldmap,map)
if(oldmap[i-1][j]==0&&!yes)/*判断上方是否可以走*/
{
FindWay(oldmap,i-1,j)
if(yes)
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
WayCopy(oldmap,map)
if(oldmap[i-1][j+1]==0&&!yes)/*判断右上方是否可以走*/
{
FindWay(oldmap,i-1,j+1)
if(yes)
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
WayCopy(oldmap,map)
if(oldmap[i+1][j-1]==0&&!yes)/*判断左下方是否可以走*/
{
FindWay(oldmap,i+1,j-1)
if(yes)
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
WayCopy(oldmap,map)
if(oldmap[i][j-1]==0&&!yes)/*判断左方是否可以走*/
{
FindWay(oldmap,i,j-1)
if(yes)
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
WayCopy(oldmap,map)
if(oldmap[i-1][j-1]==0&&!yes)/*判断左上方是否可以走*/
{
FindWay(oldmap,i-1,j-1)
if(yes)
{
way[wayn][0]=i
way[wayn++][1]=j
return
}
}
return
}
void MapRand(int (*map)[N])/*开始的随机迷宫图*/
{
int i,j
cleardevice()/*清屏*/
randomize()/*随机数发生器*/
for(i=0i<Ni++)
{
for(j=0j<Nj++)
{
if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/
map[i][j]=1
else
if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/
map[i][j]=0
else
map[i][j]=random(2)/*其它的随机生成0或1*/
}
}
}
void PrMap(int (*map)[N])/*输出迷宫图*/
{
int i,j
for(i=0i<Ni++)
for(j=0j<Nj++)
if(map[i][j]==0)
{
setfillstyle(SOLID_FILL,WHITE)/*白色为可走的路*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6)
}
else
{
setfillstyle(SOLID_FILL,BLUE)/*蓝色为墙壁*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6)
}
}
void Find(void)/*找到通路*/
{
int i
setfillstyle(SOLID_FILL,RED)/*红色输出走的具体路线*/
wayn--
for(i=wayni>=0i--)
{
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+
way[i][1]*15+6,50+way[i][0]*15+6)
sleep(1)/*控制显示时间*/
}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+
(N-2)*15+6,50+(N-2)*15+6)/*在目标点标红色*/
setcolor(GREEN)
settextstyle(0,0,2)/*设置字体大小*/
outtextxy(130,400,"Find a way!")
}
void NotFind(void)/*没找到通路*/
{
setcolor(GREEN)
settextstyle(0,0,2)/*设置字体大小*/
outtextxy(130,400,"Not find a way!")
}
void Result(void)/*结果处理*/
{
if(yes)/*如果找到*/
Find()
else/*没找到路*/
NotFind()
getch()
}
void Close(void)/*图形关闭*/
{
closegraph()
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）