#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)/*下*/ elseif(c=='z'&&map[x+1][y-1]!=1)DrawPeople(&x,&y,6)/*左下*/elseif(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()}
#include<stdio.h>#include<conio.h>
int migong[10][10]= //设置迷宫，最外围1为墙 里边0为可走路径 1为障碍
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,1,0,0,1},
{1,0,1,0,0,0,0,0,0,1},
{1,0,0,0,1,0,1,1,1,1},
{1,1,1,1,0,0,1,1,1,1},
{1,0,0,0,0,1,1,1,1,1},
{1,0,1,1,0,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
}
int num
struct
{
int x,y,d
}lj[100]//x,y分别为垂直和水平方向
void start()
{
int top=0,x,y,d,find//d为设置方向，上下左右。find为设置找不找得到路
lj[top].x=1
lj[top].y=1
migong[1][1]=-1
find=0d=-1
while(top>-1){
if(lj[top].x==8&&lj[top].y==8)
{
printf("迷宫路径如下：\n")
printf("start->")
for(x=0x<=topx++)
{
printf("(%d,%d)-> ",lj[x].x,lj[x].y)//把找到的路径输出
num++
if(num%8==0)
printf("\n")
}
printf("->end!\n")
}
while(d<4&&find==0){
d++
switch(d){
case 0:x=lj[top].x-1 y=lj[top].y break//方向为上
case 1:x=lj[top].x y=lj[top].y+1break//方向为右
case 2:x=lj[top].x+1 y=lj[top].y break//方向为下
case 3:x=lj[top].x y=lj[top].y-1}//方向为左
if(migong[x][y]==0)
find=1
}
if(find==1){ //判断是否找得到
lj[top].d=d
top++
lj[top].x=x
lj[top].y=y
d=-1find=0 //重新调整方向
migong[x][y]=-1}
else{
migong[lj[top].x][lj[top].y]=0
top--d=lj[top].d //找不到的话退栈
}
}
}
void main()
{
start()
getch()
}
#include<stdio.h>#include<stdlib.h>
#define M 15
#define N 15
struct mark //定义迷宫内点的坐标类型
{
int x
int y
}
struct Element //"恋"栈元素，嘿嘿。。
{
int x,y//x行,y列
int d//d下一步的方向
}
typedef struct LStack //链栈
{
Element elem
struct LStack *next
}*PLStack
/*************栈函数****************/
int InitStack(PLStack &S)//构造空栈
{
S=NULL
return 1
}
int StackEmpty(PLStack S)//判断栈是否为空
{
if(S==NULL)
return 1
else
return 0
}
int Push(PLStack &S, Element e)//压入新数据元素
{
PLStack p
p=(PLStack)malloc(sizeof(LStack))
p->elem=e
p->next=S
S=p
return 1
}
int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
PLStack p
if(!StackEmpty(S))
{
e=S->elem
p=S
S=S->next
free(p)
return 1
}
else
return 0
}
/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,dint a,b
Element elem,e
PLStack S1, S2
InitStack(S1)
InitStack(S2)
maze[start.x][start.y]=2//入口点作上标记
elem.x=start.x
elem.y=start.y
elem.d=-1//开始为-1
Push(S1,elem)
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem)
i=elem.x
j=elem.y
d=elem.d+1//下一个方向
while(d<4) //试探东南西北各个方向
{
a=i+diradd[d][0]
b=j+diradd[d][1]
if(a==end.x &&b==end.y &&maze[a][b]==0) //如果到了出口
{
elem.x=i
elem.y=j
elem.d=d
Push(S1,elem)
elem.x=a
elem.y=b
elem.d=886//方向输出为-1 判断是否到了出口
Push(S1,elem)
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n")
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e)
Push(S2,e)
}
while(S2)
{
Pop(S2,e)
printf("-->(%d,%d,%d)",e.x,e.y,e.d)
}
return//跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=2//标记走过此点
elem.x=i
elem.y=j
elem.d=d
Push(S1,elem)//当前位置入栈
i=a//下一点转化为当前点
j=b
d=-1
}
d++
}
}
printf("没有找到可以走出此迷宫的路径\n")
}
/*************建立迷宫*******************/
void initmaze(int maze[M][N])
{
int i,j
int m,n//迷宫行,列 [/M]
printf("请输入迷宫的行数 m=")
scanf("%d",&m)
printf("请输入迷宫的列数 n=")
scanf("%d",&n)
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n)
for(i=1i<=mi++)
for(j=1j<=nj++)
scanf("%d",&maze[i][j])
printf("你建立的迷宫为(最外圈为强)...\n")
for(i=0i<=m+1i++) //加一圈围墙
{
maze[i][0]=1
maze[i][n+1]=1
}
for(j=0j<=n+1j++)
{
maze[0][j]=1
maze[m+1][j]=1
}
for(i=0i<=m+1i++) //输出迷宫
{
for(j=0j<=n+1j++)
printf("%d ",maze[i][j])
printf("\n")
}
}
void main()
{
int sto[M][N]
struct mark start,end//start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}}//行增量和列增量 方向依次为东西南北 [/M]
initmaze(sto)//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n")
scanf("%d,%d",&start.x,&start.y)
printf("输入出口的横坐标,纵坐标[逗号隔开]\n")
scanf("%d,%d",&end.x,&end.y)
MazePath(start,end,sto,add)//find path
system("PAUSE")
}
