Question

迷宫算法

以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。首先用二维数组存储迷宫数据，迷宫数据由用户输入。
一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）

Answer 1

#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,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(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还是不错滴o(∩_∩)o...
}
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; //迷宫行,列

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("你建立的迷宫为o(∩_∩)o...\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}};//行增量和列增量 方向依次为东西南北

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");
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#define overflow -1
#define ok 1
#define error 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef struct
{
int x;
int y;
}PosType;//位置类型

typedef struct
{
int row,col;
int a[50][50];
}MazeType;//迷宫类型

typedef struct
{
int ord;//通道块在路径上的序号
PosType seat;//通道块在迷宫中的“坐标位置”
int di;//从此通道块走向下一个通道块的方向

}SElemType;//栈的元素类型

typedef struct
{
SElemType *base;
SElemType *top;
int Stacksize;

}SqStack;//栈结构

Status InitStack(SqStack &S)//初始化栈
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) exit (overflow);
S.top=S.base;
S.Stacksize=STACK_INIT_SIZE;
return ok;
}

Status Push(SqStack &S,SElemType 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;
}

Status Pop(SqStack &S,SElemType &e)//出栈
{
if(S.top==S.base) return error;
e=*--S.top;
return ok;
}

bool StackEmpty(SqStack S)//判断栈是否为空
{
if(S.top==S.base)
return ok;
else return error;
}

Status InitMaze(MazeType &maze)//初始化迷宫
{
int i,j;
for( j=0;j<maze.col+2;j++)
maze.a[0][j]=1;
for( i=1;i<maze.row+1;i++)
{
maze.a[i][0]=1;
maze.a[i][maze.col+1]=1;
for(int j=1;j<maze.col+1;j++)
scanf("%d",&maze.a[i][j]);

}
for(j=0;j<maze.col+2;j++)
maze.a[maze.row+1][j]=1;

return ok;

}//为了避免检查边界，把迷宫的外围都设成障碍，迷宫的内核是row行，col列的数组

bool Pass(MazeType maze,PosType curpos)//判断是否可以通过
{
return maze.a[curpos.x][curpos.y]==0;

}
Status FootPrint(MazeType &maze,PosType curpos)//留下足迹
{
maze.a[curpos.x][curpos.y]=2;
return ok;
}

SElemType CreatElem(int step,PosType pos,int di)//创造一个SElemType型的数据
{
SElemType e;
e.ord=step;
e.seat=pos;
e.di=di;
return e;
}

bool IsEnd(PosType pos1,PosType pos2)//判断是否结束
{
return pos1.x==pos2.x&&pos1.y==pos2.y;

}

PosType NextPos(PosType curpos,int di)//向下一步搜索
{
PosType pos=curpos;
switch(di)
{
case 1:pos.x++;break;//向东
case 2:pos.y++;break;//向南
case 3:pos.x--;break;//向西
case 4:pos.y--;break;//向北
}
return pos;
}

Status MarkPrint(MazeType &maze,PosType curpos)//在死路处留下印迹
{
maze.a[curpos.x][curpos.y]='*';
return ok;
}

Status MazePath(MazeType &maze,PosType start,PosType end)//寻找路径
{
//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），
//并返回ture；否则返回false
SqStack S;
SElemType e;
InitStack(S);
PosType curpos=start;//设定当前位置为入口位置
int curstep=1;//探索第一步
do{
if(Pass(maze,curpos))
{
FootPrint(maze,curpos);//留下足迹
e=CreatElem(curstep,curpos,1);
Push(S,e);//加入路径
if(IsEnd(curpos,end))
return ok;//达到终点
curpos=NextPos(curpos,1);//下一步是当期位置的东邻
curstep++;//探索下一步
}
else//当前位置不能通过
{
if(!StackEmpty(S))
{
Pop(S,e);
while(e.di==4&&!StackEmpty(S))
{
MarkPrint(maze,e.seat);//留下不能通过的标记，并退一步
Pop(S,e);

}
if(e.di<4)
{
e.di++;//换下一个方向
Push(S,e);
curpos=NextPos(e.seat,e.di);//设定当前位置是新方向上的相邻块

}
}
}
}while(!StackEmpty(S));
return error;

}

Status PrintMaze(MazeType maze)//输出迷宫
{
int i,j;
for(i=0;i<maze.row+2;i++)
{
for(j=0;j<maze.col+2;j++)
printf("%d ",maze.a[i][j]);
printf("\n");
}
return ok;

}

void main()
{
MazeType maze;
printf("请输入迷宫的行数row和列数col：");
scanf("%d %d",&maze.row,&maze.col);
printf("请输入迷宫数据，0表示通道，1表示障碍：\n");
InitMaze(maze);
PosType start,end;
start.x=1;start.y=1;
end.x=maze.row;end.y=maze.col;
if(MazePath(maze,start,end))
{
printf("迷宫走法（2代表走法，*代表不通）\n");
PrintMaze(maze);
}
else
printf("没有找到通路!\n");

}
给你参考一下。