function maze
row=20
col=39
rand('state',sum(100*clock))
[cc,rr]=meshgrid(1:col,1:row)
state = reshape([1:row*col],row,col)
id = reshape([1:row*col],row,col)
ptr_left = zeros(size(id))
ptr_up = zeros(size(id))
ptr_right = zeros(size(id))
ptr_down = zeros(size(id))
ptr_left(:,2:size(id,2)) = id(:,1:size(id,2)-1)
ptr_up(2:size(id,1),:) = id(1:size(id,1)-1,:)
ptr_right(:,1:size(id,2)-1) = id(:,2:size(id,2))
ptr_down(1:size(id,1)-1,:) = id(2:size(id,1),:)
the_maze = cat(2,reshape(id,row*col,1),reshape(rr,row*col,1),reshape(cc,row*col,1),reshape(state,row*col,1),...
reshape(ptr_left,row*col,1),reshape(ptr_up,row*col,1),reshape(ptr_right,row*col,1),reshape(ptr_down,row*col,1) )
the_maze = sortrows(the_maze)
id=the_maze(:,1)
rr=the_maze(:,2)
cc=the_maze(:,3)
state=the_maze(:,4)
ptr_left=the_maze(:,5)
ptr_up=the_maze(:,6)
ptr_right=the_maze(:,7)
ptr_down=the_maze(:,8)
clear the_maze
[state, ptr_left, ptr_up, ptr_right, ptr_down]=...
make_pattern(row,col,rr, cc, state, ptr_left, ptr_up, ptr_right, ptr_down)
h=figure('KeyPressFcn',@move_spot,'color','white')
show_maze(row, col, rr, cc, ptr_left, ptr_up, ptr_right, ptr_down,h)
% 开始
cursor_pos=[1,1]
current_id=1
figure(h)
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color','r')
set(gcf,'Units','normalized')
set(gcf,'position',[0 0 1 .91])
tic
% 记录过程
while ~all(cursor_pos == [col,row])
waitfor(gcf,'CurrentCharacter')
set(gcf,'CurrentCharacter','~') % update to another character so repeats are recognized
switch double(key(1))
case 108 % left
if ptr_left(current_id)<0 % check for legal move
current_id=-ptr_left(current_id)
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color',[.8,.8,.8])
cursor_pos(1)=cursor_pos(1)-1
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color','r')
end
case 114 % right
if ptr_right(current_id)<0 % check for legal move
current_id=-ptr_right(current_id)
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color',[.8,.8,.8])
cursor_pos(1)=cursor_pos(1)+1
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color','r')
end
case 117 % up
if ptr_up(current_id)<0 % check for legal move
current_id=-ptr_up(current_id)
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color',[.8,.8,.8])
cursor_pos(2)=cursor_pos(2)-1
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color','r')
end
case 100 % down
if ptr_down(current_id)<0 % check for legal move
current_id=-ptr_down(current_id)
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color',[.8,.8,.8])
cursor_pos(2)=cursor_pos(2)+1
text(cursor_pos(1),cursor_pos(2),'\diamondsuit','HorizontalAlignment','Center','color','r')
end
otherwise
end
end
thyme=toc
title(cat(2,' Winning Time ',num2str(round(thyme*100)/100),'(sec)'),'FontSize',20)
return
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、子程序、、、、、、、、、、、、、、、、、、、、、、、、、、、、
function move_spot(src,evnt)%获取方向建
assignin('caller','key',evnt.Key)
return
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
function show_maze(row, col, rr, cc, ptr_left, ptr_up, ptr_right, ptr_down,h)
%显示迷宫
figure(h)
line([.5,col+.5],[.5,.5]) % draw top border
line([.5,col+.5],[row+.5,row+.5]) % draw bottom border
line([.5,.5],[1.5,row+.5]) % draw left border
line([col+.5,col+.5],[.5,row-.5]) % draw right border
for ii=1:length(ptr_right)
if ptr_right(ii)>0 % right passage blocked
line([cc(ii)+.5,cc(ii)+.5],[rr(ii)-.5,rr(ii)+.5])
hold on
end
if ptr_down(ii)>0 % down passage blocked
line([cc(ii)-.5,cc(ii)+.5],[rr(ii)+.5,rr(ii)+.5])
hold on
end
end
axis equal
axis([.5,col+.5,.5,row+.5])
axis off
set(gca,'YDir','reverse')
return
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
function [state, ptr_left, ptr_up, ptr_right, ptr_down]=make_pattern(row,col, rr, cc, state, ptr_left, ptr_up, ptr_right, ptr_down)%产生边界道路信息
while max(state)>1
tid=ceil(col*row*rand(15,1))
cityblock=cc(tid)+rr(tid)
is_linked=(state(tid)==1)
temp = sortrows(cat(2,tid,cityblock,is_linked),[3,2])
tid = temp(1,1)
dir=ceil(4*rand)
switch dir
case 1
if ptr_left(tid)>0 &state(tid)~=state(ptr_left(tid))
state( state==state(tid) | state==state(ptr_left(tid)) )=min([state(tid),state(ptr_left(tid))])
ptr_right(ptr_left(tid))=-ptr_right(ptr_left(tid))
ptr_left(tid)=-ptr_left(tid)
end
case 2
if ptr_right(tid)>0 &state(tid)~=state(ptr_right(tid))
state( state==state(tid) | state==state(ptr_right(tid)) )=min([state(tid),state(ptr_right(tid))])
ptr_left(ptr_right(tid))=-ptr_left(ptr_right(tid))
ptr_right(tid)=-ptr_right(tid)
end
case 3
if ptr_up(tid)>0 &state(tid)~=state(ptr_up(tid))
state( state==state(tid) | state==state(ptr_up(tid)) )=min([state(tid),state(ptr_up(tid))])
ptr_down(ptr_up(tid))=-ptr_down(ptr_up(tid))
ptr_up(tid)=-ptr_up(tid)
end
case 4
if ptr_down(tid)>0 &state(tid)~=state(ptr_down(tid))
state( state==state(tid) | state==state(ptr_down(tid)) )=min([state(tid),state(ptr_down(tid))])
ptr_up(ptr_down(tid))=-ptr_up(ptr_down(tid))
ptr_down(tid)=-ptr_down(tid)
end
otherwise
dir
error('quit')
end
end
return
程序目的：输入一个任意大小的迷宫，用栈求出一条走出迷宫的路径，并
显示在屏幕上。
程序实现：
可以实现载入迷宫和保存迷宫，附带文件中有4个测试迷宫路径的
文件test1~4.dd。请将这些文件拷贝到TC当前目录下，或者在载
入时写明完全路径。由于屏幕大小的限制，当用户自己输入迷宫
时一定要注意：迷宫大小是有限制的，不小于4*3,不大于30*20。
否则会出现错误信息。输入开始时全是墙，用上下左右键移动，
用Del键删除墙，形成通路，用Enter键添加墙。输入结束时可以
将迷宫保存下来，以dd为扩展名。输入完毕时用F9键来得到结果，
找到路径时，屏幕下方会出现Path found，否则出现Path not found。
程序经Turbo C 2.0编译调试成功。运行时不用添加任何运行库。
不可以在VC上编译。
下载DOS版和windows版的迷宫游戏全部代码
用户名：migong
----------------------------------------------------------------------------------
/**//*
MazePath Demo BY Turbo C 2.0
Copyright(c) RoverUnion. All right reserved.
Filename: Maze.c
Author Dongchengyu.
Ver 1.10
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
#include <dos.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define F9 0x43
#define Esc 0x1b
#define Del 0x53
#define Home 0x47
#define End 0x4f
#define Space 0x20
#define Up 0x48
#define Down 0x50
#define Left 0x4b
#define Right 0x4d
#define Enter 0x0d
#define F2 0x3c
#define F3 0x3d
#define STACK_INIT_SIZE 200
#define STACKINCREMENT 10
typedef int Boolean
typedef int Status
typedef struct {
int x
int y
} PosType
typedef struct {
int ord
PosType seat
int di
} SElemType
typedef struct {
int td
int foot
int mark
} MazeType
typedef struct {
SElemType *base
SElemType *top
int stacksize
} Stack
int Maze[20][30]
MazeType maze[20][30]
PosType StartPlace
PosType EndPlace
int count
int m,n
Boolean b_start=FALSE,b_end=FALSE
void CreatMaze(void)
Status SaveMaze(char *filename)
Status LoadMaze(char *filename)
void Error(char *message)
Status InitStack(Stack *s)
Status DestroyStack(Stack *s)
Status ClearStack(Stack *s)
Boolean StackEmpty(Stack *s)
int StackLength(Stack *s)
Status Push(Stack *s,SElemType e)
SElemType Pop(Stack *s,SElemType e)
Status GetTop(Stack *s,SElemType *e)
Status StackTraverse(Stack *s,Status (* visit)(SElemType *se))
Boolean Pass(PosType curpos)
void MarkPrint(PosType seat)
void FootPrint(PosType curpos)
PosType NextPos(PosType seat,int di)
Status MazePath(PosType start,PosType end)
void CreatMaze(void)
/**//* Form the maze. */
{
void Error(char *message)
Status SaveMaze(char *filename)
Status LoadMaze(char *filename)
int i,j
int x,y
char c
char savename[12],loadname[12]
Boolean flag=FALSE,load=FALSE
clrscr()
printf("Menu:\n\n")
printf("1.Load Mazefile:(*.dd)\n\n")
printf("2.Input Maze:\n\n")
printf("Input your choice: ")
do
{
c=getch()
switch(c)
{
case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''')break
case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''')break
case Esc: sleep(1)exit(1)
default: break
}
}
while(c!=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''&&c!=''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''')
if(c==''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''')
{
printf("\n\nLoadName: ")
scanf("%s",loadname)
if(LoadMaze(loadname))
{
sleep(1)load=TRUE
}
else { gotoxy(1,9)printf("Load fail! ")}
}
if(!load)
{
printf("\nInput the maze''''''''''''''''''''''''''''''''s size:\n")
printf("\nInput Length :\n")
scanf("%d",&m)
printf("\nInput Width :\n")
scanf("%d",&n)
if(m<4||n<4) Error("Input")
if(m>30||n>20) Error("Maze too large")
for(i=0i<30i++)
for(j=0j<20j++)
Maze[j][i]=2
StartPlace.x=0
StartPlace.y=0
EndPlace.x=0
EndPlace.y=0
clrscr()
printf("\n")
for(i=1i<=ni++)
{
for(j=1j<=mj++)
{
printf(" #")
Maze[i-1][j-1]=0
}
printf("\n")
}
}
gotoxy(65,5)
printf("''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''':Wall")
gotoxy(65,7)
printf("Start:Home")
gotoxy(65,9)
printf("End:End")
gotoxy(65,11)
printf("Delete Wall:Del")
gotoxy(65,13)
printf("Enter Wall:Enter")
gotoxy(65,15)
printf("Save Maze:F2")
gotoxy(65,17)
printf("Complete:F9")
gotoxy(65,19)
printf("Exit:Esc")
gotoxy(4,3)
x=4y=3
do
{
c=getch()
switch(c)
{
case Up: if(y>3) { y--gotoxy(x,y)}
break
case Down: if(y<n) { y++gotoxy(x,y)}
break
case Left: if(x>4) { x-=2gotoxy(x,y)}
break
case Right: if(x<2*m-2) { x+=2gotoxy(x,y)}
break
case Del: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) b_start=FALSE
if(y-2==EndPlace.y&&x/2-1==EndPlace.x) b_end=FALSE
putch('''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''')Maze[y-2][x/2-1]=1gotoxy(x,y)
break
case Enter: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) break
if(y-2==EndPlace.y&&x/2-1==EndPlace.x) break
putch(''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''')Maze[y-2][x/2-1]=0gotoxy(x,y)
break
case Home: if(Maze[y-2][x/2-1]&&!b_start)
{
StartPlace.x=x/2-1
StartPlace.y=y-2
putch(''''''''''''''''''''''''''''''''S'''''''''''''''''''''''''''''''')
gotoxy(x,y)
b_start=TRUE
}
break
case End: if(Maze[y-2][x/2-1]&&!b_end)
{
EndPlace.x=x/2-1
EndPlace.y=y-2
putch(''''''''''''''''''''''''''''''''E'''''''''''''''''''''''''''''''')
gotoxy(x,y)
b_end=TRUE
}
break
case Esc: gotoxy(2,22)printf("exit")sleep(1)exit(1)
case F9: if(b_start&&b_end) flag=TRUEbreak
case F2: gotoxy(2,22)
printf("Savename:")
scanf("%s",savename)
gotoxy(2,22)
if(SaveMaze(savename)) printf("Save OK! ")
else printf("Save fail! ")
sleep(1)
gotoxy(2,22)
printf(" ")
gotoxy(x,y)
break
default: break
}
}
while(!flag)
for(i=0i<30i++)
for(j=0j<20j++)
{
maze[j][i].td=Maze[j][i]
maze[j][i].mark=0
maze[j][i].foot=0
}
}
Status LoadMaze(char *file)
/**//* The maze has been loaded. */
{
FILE *fp
char *buffer
char ch
int i=0,j,k
Boolean len=FALSE,wid=FALSE
if((fp=fopen(file,"r"))==NULL)
return ERROR
buffer=(char *)malloc(600*sizeof(char))
ch=fgetc(fp)
while(ch!=EOF)
{
buffer[i]=ch
i++
ch=fgetc(fp)
}
m=30n=20
for(i=0i<600i++)
{
j=i/30k=i%30
if(buffer[i]==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!len){ m=ilen=TRUE}
if(k==0&&buffer[i]==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!wid){ n=jwid=TRUE}
switch(buffer[i])
{
case ''''''''''''''''''''''''''''''''0'''''''''''''''''''''''''''''''': Maze[j][k]=0break
case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': Maze[j][k]=1break
case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': Maze[j][k]=2break
case ''''''''''''''''''''''''''''''''3'''''''''''''''''''''''''''''''': Maze[j][k]=1
StartPlace.x=k
StartPlace.y=j
b_start=TRUE
break
case ''''''''''''''''''''''''''''''''4'''''''''''''''''''''''''''''''': Maze[j][k]=1
EndPlace.x=k
EndPlace.y=j
b_end=TRUE
break
default : break
}
}
fclose(fp)
clrscr()
for(i=0i<30i++)
for(j=0j<20j++)
{
maze[j][i].td=Maze[j][i]
maze[j][i].foot=0
maze[j][i].mark=0
if(Maze[j][i]==0)
{
gotoxy(2*i+2,j+2)
putch(''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''')
}
}
gotoxy(2*StartPlace.x+2,StartPlace.y+2)
putch(''''''''''''''''''''''''''''''''S'''''''''''''''''''''''''''''''')
gotoxy(2*EndPlace.x+2,EndPlace.y+2)
putch(''''''''''''''''''''''''''''''''E'''''''''''''''''''''''''''''''')
return OK
}
Status SaveMaze(char *filename)
/**//* The maze has been saved. */
{
FILE *fp
char *buffer
int i,j,k
fp=fopen(filename,"wb")
buffer=(char *)malloc(600*sizeof(char))
for(i=0i<600i++)
{
j=i/30k=i%30
switch(Maze[j][k])
{
case 0: buffer[i]=''''''''''''''''''''''''''''''''0''''''''''''''''''''''''''''''''break
case 1: buffer[i]=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''break
case 2: buffer[i]=''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''break
default : Error("Write")break
}
if(k==StartPlace.x&&j==StartPlace.y) buffer[i]=''''''''''''''''''''''''''''''''3''''''''''''''''''''''''''''''''
if(k==EndPlace.x&&j==EndPlace.y) buffer[i]=''''''''''''''''''''''''''''''''4''''''''''''''''''''''''''''''''
}
fwrite(buffer,600,1,fp)
free(buffer)
fclose(fp)
return OK
}
void Error(char *message)
{
clrscr()
fprintf(stderr,"Error:%s\n",message)
exit(1)
} /**//* Error */
Status InitStack(Stack *s)
/**//* The stack s has been created and is initialized to be empty. */
{
s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))
if(!s->base) Error("Overflow")
s->top=s->base
s->stacksize=STACK_INIT_SIZE
return OK
} /**//* InitStack */
Status DestroyStack(Stack *s)
/**//* The stack s has been destroyed. */
{
s->top=NULL
s->stacksize=0
free(s->base)
s->base=NULL
return OK
} /**//* DestroyStack */
Status ClearStack(Stack *s)
/**//* The stack has been clear to be maximum. */
{
s->top=s->base
s->stacksize=STACK_INIT_SIZE
return OK
} /**//* ClearStack */
Boolean StackEmpty(Stack *s)
/**//* Check if the stack s is empty. */
{
if(s->top==s->base) return TRUE
else return FALSE
} /**//* StackEmpty */
int StackLength(Stack *s)
/**//* Gain the length of the stack s. */
{
if(s->top>s->base) return (int)(s->top-s->base)
else return 0
} /**//* StackLength */
Status Push(Stack *s,SElemType e)
/**//* The element e has been pushed into the stack s. */
{
if(s->top-s->base>=s->stacksize)
{
s->base=(SElemType *)realloc(s->base,
(s->stacksize+STACKINCREMENT)*sizeof(SElemType))
if(!s->base) Error("Overflow")
s->top=s->base+s->stacksize
s->stacksize+=STACKINCREMENT
}
*s->top++=e
return OK
} /**//* Push */
SElemType Pop(Stack *s,SElemType e)
/**//* The element e has been removed from the stack s. */
{
if(s->top==s->base) Error("Pop")
e=*--s->top
return e
} /**//* Pop */
Status GetTop(Stack *s,SElemType *e)
/**//* The element e has got to the top of the stack s.*/
{
if(s->top==s->base) Error("GetTop")
*e=*(s->top-1)
return OK
} /**//* GetTop */
/**//* Traverse the stack s using ''''''''''''''''''''''''''''''''visiting'''''''''''''''''''''''''''''''' function. */
/**//* Status StackTraverse(Stack *s,Status (* visit)(SElemType *se))
{
SElemType p
int result
if(s->top==s->base) return ERROR
p=s->base
while(!(p==s->top))
{
result=(*visit)(p)
p++
}
return OK
} */
Boolean Pass(PosType curpos)
/**//* Check if the current position can be passed. */
{
if(maze[curpos.x][curpos.y].td==1&&
maze[curpos.x][curpos.y].foot==0&&maze[curpos.x][curpos.y].mark==0)
return TRUE
else return FALSE
} /**//* Pass */
void MarkPrint(PosType seat)
/**//* Mark the position seat. */
{
maze[seat.x][seat.y].mark=-1
/**//* Marking ''''''''''''''''''''''''''''''''-1'''''''''''''''''''''''''''''''' symbolize the current position cannot be put. */
} /**//* MarkPrint */
void FootPrint(PosType curpos)
/**//* The foot of the curpos of the maze has been set ''''''''''''''''''''''''''''''''true''''''''''''''''''''''''''''''''. */
{
maze[curpos.x][curpos.y].foot=1
} /**//* FootPrint */
PosType NextPos(PosType seat,int di)
{
switch(di)
{
case 1: seat.y++return seat/**//* Eastward */
case 2: seat.x++return seat/**//* Southward */
case 3: seat.y--return seat/**//* Westward */
case 4: seat.x--return seat/**//* Northward */
default: seat.x=0seat.y=0return seat
}
} /**//* NextPos */
/**//* The key to the program. */
/**//* Pre: The maze array &the startplace &the endplace.
Post: Find the one traverse of the maze and perform the mazepath.
Uses: The ADT stack class.
*/
Status MazePath(PosType start,PosType end)
{
PosType curpos
int curstep
SElemType e
Stack *s,stack
stack.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))
if(!stack.base) Error("Overflow")
stack.top=stack.base
stack.stacksize=STACK_INIT_SIZE
s=&stack
curpos=start
curstep=1
do
{
if(Pass(curpos))
{
FootPrint(curpos)
e.ord=curstepe.seat=curpose.di=1
gotoxy((curpos.y+1)*2,curpos.x+2)
putch(''''''''''''''''''''''''''''''''@'''''''''''''''''''''''''''''''')
delay(8000)/**//* pospone time. */
Push(s,e)
if(curpos.x==end.x&&curpos.y==end.y) /**//* Proceed recursively. */
{
DestroyStack(s)
return TRUE
}
curpos=NextPos(curpos,1)/**//* Try next position. */
curstep++
}
else
{
if(!StackEmpty(s))
{
e=Pop(s,e)/**//* Removed e from s. */
while(e.di==4&&!StackEmpty(s)) /**//* Four directions have been checked
and s is not empty. */
{
MarkPrint(e.seat)
gotoxy((e.seat.y+1)*2,e.seat.x+2)
putch(''''''''''''''''''''''''''''''''@'''''''''''''''''''''''''''''''')
delay(8000)/**//* Pospone time. */
gotoxy((e.seat.y+1)*2,e.seat.x+2)
putch('''''''''''''''''''''''''''''''' '''''''''''''''''''''''''''''''')
e=Pop(s,e)/**//* Remove e from s. */
curstep--
}
if(e.di<4) /**//* The current position hasnot been checked. */
{
e.di++
Push(s,e)/**//* Insert e into s. */
curpos=NextPos(e.seat,e.di)/**//* Try next position. */
}
}
}
}
while(!StackEmpty(s))
DestroyStack(s)
return FALSE
} /**//* MazePath */
void main()
{
PosType start,end
CreatMaze()
start.x=StartPlace.y
start.y=StartPlace.x
end.x=EndPlace.y
end.y=EndPlace.x
if(MazePath(start,end))
{
gotoxy(2,22)
printf("Path found\n")
}
else
{
gotoxy(2,22)
printf("Path not found\n")
}
getch()
clrscr()
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）