189 8069 5689
全部程序分几个文件，看清楚了，每段程序放入一个文件，每段程序前面都有文件名：
发展壮大离不开广大客户长期以来的信赖与支持，我们将始终秉承“诚信为本、服务至上”的服务理念，坚持“二合一”的优良服务模式，真诚服务每家企业，认真做好每个细节，不断完善自我，成就企业，实现共赢。行业涉及成都凿毛机等，在重庆网站建设公司、全网整合营销推广、WAP手机网站、VI设计、软件开发等项目上具有丰富的设计经验。
//stackoperation.cpp
Status InitStack(SqStack S)
{ //构造一个空栈S
S.base = (SElemType *)malloc(RANGE*sizeof(SElemType));
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top = S.base;
S.stacksize = RANGE;
return OK;
}//Initstack
Status 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(OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}//Push
Status Pop(SqStack S,SElemType e){
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
否则返回ERROR*/
if(S.top == S.base) return ERROR;
e = * --S.top;
return OK;
}//Pop
bool StackEmpty(SqStack S)
{ //判断栈是否为空并返回TURN或FALSE
if(S.top == S.base) return TURE;
return FALSE;
}//StackEmpty
void PrintStack()
{
SqStack ST;
SElemType e;
InitStack(ST);
do{
Pop(SqS,e);
Push(ST,e);
}while(!StackEmpty(SqS));
do{
Pop(ST,e);
printf("(%d,%d,%d)",e.seat.i,e.seat.j,e.di);
}while(!StackEmpty(ST));
}
//migong.cpp
#include "Basetype.h"
#include "stackoperation.cpp"
#include "Mazeoperation.cpp"
void main()
{
char filename[15];
FILE *fp;
printf("请输入迷宫数据文件名（长度不超过15个字符）：");
scanf("%s",filename);
//如找不到文件，则要求重新输入（最多三次机会）
for(int i=0;i3;i++){
if((fp = fopen(filename,"r")) == NULL)
{printf("不能打开文件,请重新输入文件名（长度不超过15个字符）：\n");
scanf("%s",filename);
}//if
break;
}//for
//读取迷宫的行数和列数
int rnum,cnum;
fscanf(fp,"%d,%d",rnum,cnum);
printf("这个迷宫有%d行，%d列\n",rnum,cnum);
if(rnumRANGE-2 || cnumRANGE-2)
{ printf("迷宫太大，无法求解\n");
return;
}//判断迷宫的大小是否符合要求
//初始化一个迷宫变量
MazeType maze;
for(i=0;i=rnum+1;i++)
for(int j=0;j=cnum+1;j++)
maze.arr[i][j] = '#';
CreatMaze(maze,rnum,cnum,fp);//创建迷宫
fclose(fp);//关闭迷宫文件
//打印当前迷宫
printf("当前迷宫为：\n");
for(i=0;i=rnum+1;i++)
{ for(int j=0;j=cnum+1;j++)
printf("%c",maze.arr[i][j]);
printf("\n");
}
printf("其中'#'表示障碍,外围一圈'#'为围墙\n");
//读取入口及出口位置
PosType startp,endp;
printf("请输入入口位置（两数中间以逗号相隔）：");
scanf("%d,%d",startp.i,startp.j);
printf("请输入出口位置（两数中间以逗号相隔）：");
scanf("%d,%d",endp.i,endp.j);
if(MazePath(maze,startp,endp))
{ PrintMaze(maze,rnum,cnum);//将求解的迷宫输出到文件保存，并打印到屏幕
PrintStack();//如果存在路径则打印之
}
else printf("此迷宫不存在路径\n");
}//main
//Mazeoperation.cpp
bool Pass(MazeType maze,PosType curpos)
{ //判断当前位置是否可通，并返回值
switch(char ch = maze.arr[curpos.i][curpos.j])
{ case' ': return(FALSE);
case'#':
case'@':
case'*': return(TURE);
default: { printf("迷宫中第%d行,第%d列出现不明字符%c\n",
curpos.i,curpos.j,ch);exit(0);}
}//switch
}//pass
void FootPrint(MazeType maze,PosType curpos)
{
maze.arr[curpos.i][curpos.j] = '*';
}//FootPrint
void MarkPrint(MazeType maze,PosType curpos)
{
maze.arr[curpos.i][curpos.j] = '@';
}//MarkPrint
void NextPos(PosType curpos,int di)
{
switch(di)
{ case 1: curpos.j++;break;
case 2: curpos.i++;break;
case 3: curpos.j--;break;
case 4: curpos.i--;break;
default: printf("当前方向%d无效\n",di);
exit(0);
}//switch
}//NextPos
bool MazePath(MazeType maze,PosType start,PosType end){
SElemType e;
InitStack(SqS);
PosType curpos = start;
int curstep = 1;
do{
if(!Pass(maze,curpos)){
FootPrint(maze,curpos);
e.order = curstep;
e.seat.i = curpos.i;e.seat.j = curpos.j;
e.di = 1;
Push(SqS,e);
if(curpos.i == end.i curpos.j == end.j) return(TURE);
NextPos(curpos,1);
curstep++;
}//if
else{
if(!StackEmpty(SqS)){
Pop(SqS,e);
while(e.di == 4 !StackEmpty(SqS)){
MarkPrint(maze,e.seat); Pop(SqS,e);
}//while
if(e.di4){
e.di++; Push(SqS,e);
NextPos(e.seat,e.di);
curpos.i = e.seat.i;curpos.j = e.seat.j;
}//if
}//if
}//else
}while(!StackEmpty(SqS));
return(FALSE);
}//Mazepath
void CreatMaze(MazeType maze,int row,int col,FILE *fp){
//建立迷宫
char ch = fgetc(fp);
for(int i=1;i=row;i++)
{
for(int j=1;j=col;j++)
{switch( ch = fgetc(fp))
{
case'0': maze.arr[i][j]=' ';break;
case'1': maze.arr[i][j]='#';break;
default: printf("迷宫第%d行第%d列数据为%c有错误",i,j,ch);exit(0);
}//switch
}//for
fseek(fp,2,1);
}//for
fclose(fp);
}//CreatMaze
void PrintMaze(MazeType maze,int row,int col)
{ //打印结果并输出到文件保存
FILE *out;
if((out = fopen("outfile","w"))==NULL)
{ printf("不能打开文件\n");
exit(0);
}//if
for(int i=0;i=row+1;i++)
{for(int j=0;j=col+1;j++)
{ fputc(maze.arr[i][j],out);
printf("%c",maze.arr[i][j]);
}
printf("\n");
}
printf("其中'*'号代表路径，'#'代表障碍,'@'代表死胡同\n");
fclose(out);//关闭文件
}
//Basetype.h
#include stdio.h
#include "stdlib.h"
#define RANGE 30 //栈的存储空间初始分配量，
//以及用来存放迷宫的字符数组的最大维数
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define STACKINCREMENT 5 //栈的存储空间分配增量
typedef struct{
int i; //行坐标
int j; //列坐标
}PosType; //迷宫中坐标位置类型
//栈的定义
typedef struct{
int order; //通道块在路径上的“方向”
PosType seat; //通道块在迷宫中的“坐标位置”
int di; //从此通道块走向下一通道块的“方向”
}SElemType; //栈的元素类型
typedef struct{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;
//迷宫的定义
typedef struct{
int m,n;
char arr[RANGE][RANGE];
}MazeType;
typedef int Status;
SqStack SqS; //定义一个栈
#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
找到，
没找到
*/
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-2y==N-2)/*人工控制找成功的话*/ yes=1; /*如果成功标志为1*/ }
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */ {
int i,j;
for(i=0;iN;i++) for(j=0;jN;j++) oldmap[i][j]=map[i][j]; }
int FindWay(int (*map)[N],int i,int j)/*递归找路*/ {
if(i==N-2j==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=0;iN;i++) {
for(j=0;jN;j++) { if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/ map[i][j]=1; else if(i==1j==1||i==N-2j==N-2)/*出发点与终点表示为可走的*/ map[i][j]=0; else map[i][j]=random(2);/*其它的随机生成0或1*/ } } }
void PrMap(int (*map)[N])/*输出迷宫图*/ {
int i,j;
for(i=0;iN;i++) for(j=0;jN;j++) 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=wayn;i=0;i--) {
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(); }
#includestdio.h
#includemalloc.h
int N;
int **maze;
int zx,zy;
void PrintMaze(int N){
int *l[2],i,j;
l[0]=(int*)malloc(sizeof(l)*N*N);
l[1]=(int*)malloc(sizeof(l)*N*N);
for(i=0;iN*N;i++){
l[0][i]=-1;
}
for(i=0;iN;i++){
for(j=0;jN;j++){
if(maze[i][j]1){
l[0][maze[i][j]-2]=i;
l[1][maze[i][j]-2]=j;
}
}
}for(i=0;iN*N;i++){
if(l[0][i]!=-1)printf("(%d,%d)\n",l[0][i]+1,l[1][i]+1);
else break;
}
}int SelMaze(int x,int y){
if(x9||y9||x0||y0)return(0);
return(!maze[x][y]);
}int FindMaze(int x,int y,int m){
if(x==zxy==zy){
maze[x][y]=m;
return(1);
}
if(SelMaze(x+1,y)){
maze[x][y]=m;
if(FindMaze(x+1,y,m+1))PrintMaze(N);
maze[x][y]=0;
}if(SelMaze(x,y+1)){
maze[x][y]=m;
if(FindMaze(x,y+1,m+1))PrintMaze(N);
maze[x][y]=0;
}if(SelMaze(x,y-1)){
maze[x][y]=m;
if(FindMaze(x,y-1,m+1))PrintMaze(N);
maze[x][y]=0;
}if(SelMaze(x-1,y)){
maze[x][y]=m;
if(FindMaze(x-1,y,m+1))PrintMaze(N);
maze[x][y]=0;
}
return(0);
}
int main(){
int x,y,i,j;
scanf("%d\n%d%d%d%d",N,x,y,zx,zy);
zx--;zy--;x--;y--;
maze=(int**)malloc(sizeof(int*)*N);
for(i=0;iN;i++){
maze[i]=(int*)malloc(sizeof(maze)*N);
for(j=0;jN;j++){
scanf("%d",maze[i][j]);
}
}
if(!FindMaze(x,y,2))printf("No");
return(0);
}
#includestdio.h
#includeconio.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=0;d=-1;
while(top-1){
if(lj[top].x==8lj[top].y==8)
{
printf("迷宫路径如下：\n");
printf("start-");
for(x=0;x=top;x++)
{
printf("(%d,%d)- ",lj[x].x,lj[x].y);//把找到的路径输出
num++;
if(num%8==0)
printf("\n");
}
printf("-end!\n");
}
while(d4find==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+1;break;//方向为右
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=-1;find=0; //重新调整方向
migong[x][y]=-1;}
else{
migong[lj[top].x][lj[top].y]=0;
top--;d=lj[top].d; //找不到的话退栈
}
}
}
void main()
{
start();
getch();
}
#includestdio.h
#includestdlib.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,d;int 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(d4) //试探东南西北各个方向
{
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=1;i=m;i++)
for(j=1;j=n;j++)
scanf("%d",maze[i][j]);
printf("你建立的迷宫为(最外圈为强)...\n");
for(i=0;i=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i=m+1;i++) //输出迷宫
{
for(j=0;j=n+1;j++)
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");
}
#includestdio.h
#define MaxSize 20
typedef struct{
int i;
int j;
}BOX;
typedef struct{
BOX data[MaxSize];
int length;
}PathType;
void display(PathType path)
{
static int time = 0;
int k;
printf("输出第%d条路径:\n", ++time);
for (k = 0; kpath.length; k++)
printf(" (%d %d)", path.data[k].i, path.data[k].j);
printf("\n");
}
void mgpath(int mg[20][20], int xi, int yi, int x2, int y2, PathType path)
{
int di, i, j;
if (xi == x2yi == y2)
{
path.data[path.length].i = xi;
path.data[path.length].j = yi;
path.length++;
display(path);
}
else{
if (mg[xi][yi] == 0)
{
di = 0;
while (di4)
{
path.data[path.length].i = xi;
path.data[path.length].j = yi;
path.length++;
switch (di)
{
case 0:
i = xi - 1;
j = yi;
break;
case 1:
i = xi;
j = yi + 1;
break;
case 2:
i = xi + 1;
j = yi;
break;
case 3:
i = xi;
j = yi - 1;
break;
}
mg[xi][yi] = -1;
mgpath(mg, i, j, x2, y2, path);
mg[xi][yi] = 0;
path.length--;
di++;
}
}
}
}
int main()
{
PathType path;
int i, j;
int M, N;
int x1, x2, y1, y2;
int mg[20][20];
scanf_s("%d%d", M, N);
for (i = 0; iM; i++)
for (j = 0; jN; j++)
{
scanf_s("%d", mg[i][j]);
}
scanf_s("%d%d%d%d", x1, y1, x2, y2);
path.length = 0;
mgpath(mg, x1,y1,x2,y2,path);
return 0;
}