本文目录一览：
- 1、C语言用图的广度优先遍历做漫步迷宫问题
- 2、C语言 老鼠走迷宫
- 3、如何用C语言编写一个迷宫程序？
- 4、C语言迷宫找出路问题。帮画个流程图。比如下图
- 5、用C语言编写一个迷宫程序，知道出处也行 ~~！
C语言用图的广度优先遍历做漫步迷宫问题
这是我们老师给我们上数据结构课的课件
#include "stdio.h"
typedef int datatype; /*假定线性表元素的类型为整型*/
#define maxsize 1024 /*假定线性表的最大长度为1024*/
# define n 100 /* 图的顶点最大个数 */
typedef char VEXTYPE; /* 顶点的数据类型 */
typedef float ADJTYPE; /* 权值类型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 顶点信息数组 */
ADJTYPE arcs[n][n] ; /* 边权数组 */
int num ; /* 顶点的实际个数 */
}GRAPH;
/***********************1。置空图**********************/
void GraphInit(GRAPH *L)
{
L-num=0;
}
/***********************2。求结点数**********************/
int GraphVexs(GRAPH *L)
{
return(L-num);
}
/***********************3。创建图**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("请输入顶点数目：");
scanf("%d",L-num);
printf("请输入各顶点的信息(单个符号）：");
for(i=0;iL-num;i++)
{
fflush(stdin);
scanf("%c",L-vexs[i]);
}
printf("请输入边权矩阵的信息：");
for(i=0;iL-num;i++)
{
for(j=0;jL-num;j++)
{
scanf("%f",L-arcs[i][j]);
}
}
printf("图已经创建完毕！");
}
/***********************4。图的输出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("\n图的顶点数目为：%d",L.num);
printf("\n图的各顶点的信息为：\n");
for(i=0;iL.num;i++)
printf("%c ",L.vexs[i]);
printf("\n图的边权矩阵的信息为：\n");
for(i=0;iL.num;i++)
{
for(j=0;jL.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("\n");
}
printf("图已经输出完毕！");
}
/***********************5。图的深度周游**********************/
void DFS(GRAPH g,int qidian,int mark[])
//从第qidian个点出发深度优先周游图g中能访问的各个顶点
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1g.num;v1++)
{
if(g.arcs[qidian][v1]!=0mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。图的深度周游**********************/
void GraphDFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n深度周游：");
printf("\n请输入起点的下标：");
scanf("%d",qidian);
for(v=0;vg.num;v++)
{
mark[v]=0;
}
for(v=qidian;vg.num+qidian;v++)
{
//printf("v=%d ",v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //队列元素的数据类型
typedef struct
{
DATATYPE data[maxsize]; //队中元素
int front,rear; //队头元素下标、队尾元素后面位置的下标
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//将顺序循环队列sq置空（初始化）
{
sq-front=0;
sq-rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果顺序循环队列sq为空，成功返回1，否则返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0
{
if (QueueIsEmpty(sq))
else
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//将元素x入队列sq的队尾，成功返回1，失败返回0
{
if (sq-front==(sq-rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq-data[sq-rear]=x;
sq-rear=(sq-rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//将队列sq队首元素出队列，成功返回1,失败返回0
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq-front=(sq-front+1)%maxsize;
return 1;
}
}
/***********************7。图的广度周游**********************/
void BFS(GRAPH g,int v,int mark[])
//从v出发广度优先周游图g中能访问的各个顶点
{
int v1,v2;
SEQQUEUE q;
QueueInit(q);
QueueIn(q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,v1);
QueueOut(q);
for(v2=0;v2g.num;v2++)
{
if(g.arcs[v1][v2]!=0mark[v2]==0)
{
QueueIn(q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
/***********************8。图的广度周游**********************/
void GraphBFS(GRAPH g)
//深度优先周游图g中能访问的各个顶点
{
int qidian,v,v1,mark[maxsize];
printf("\n广度周游：");
printf("\n请输入起点的下标：");
scanf("%d",qidian);
for(v=0;vg.num;v++)
{
mark[v]=0;
}
for(v=qidian;vg.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
/***********************主函数**********************/
void main()
{
GRAPH tu;
GraphCreate(tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}
C语言 老鼠走迷宫
可以给你点提示：迷宫 可用个二维数组表示。求解方法是：从入口出发，顺某个方向走，若能过去，继续；否则，沿着原路返回，换方向继续走，直到所有可能的通路都被找到为止。为保证在任何位置上都能沿原路退回，需要一个先进后出的栈结构保存从入口到当前位置的路径。这里，给个算法的思想，不实现图形界面了。假设迷宫数据存放在一txt中：
迷宫数据
8 8 //迷宫的大小，行数与列数
1 1 8 8 //1 1 表入口位置 8 8 表出口位置
0 0 1 0 0 0 1 0 //以下表迷宫，1表示墙、0表示通路，为避免走的过程中越界，最好在四周加上以堵墙。
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 1 0 0 0 0 0 0
#include stdio.h
#include stdlib.h
#define MAXSIZE 50
#define ERROR -1
#define OK 0
#define FALSE 0
#define TRUE 1
typedef enum{RIGHT,DOWN,LEFT,UP} Direction;
typedef enum{YES,NO} MarkTag;
typedef struct position{ //迷宫中位置的坐标
int x;
int y;
}Position;
typedef struct{ //当前位置在路径中的序号
int order; //当前位置在迷宫中的坐标
Position seat; //从当前位置走到下一位置的方向
Direction di; //栈元素的类型
}SElemType;
typedef struct{
SElemType *elem;
int top;
}Stack;
char maze[MAXSIZE+2][MAXSIZE+2]; //用二维数组表示迷宫
int InitStack(Stack *S){ //创建一个空栈
S-elem=(SElemType *)malloc(MAXSIZE*MAXSIZE*sizeof(SElemType));
if(!S-elem)
return ERROR;
S-top=0;
return OK;
}
int Push(Stack *S,SElemType e){ //元素e入栈
if(S-top=MAXSIZE*MAXSIZE)
return ERROR;
S-elem[S-top++]=e;
return OK;
}
int Pop(Stack *S,SElemType e){ //栈顶元素出栈，由e带回栈顶元素
if(S-top=0)
return ERROR;
*e=S-elem[--S-top];
return OK;
}
int Empty(Stack S){ //若栈为空，返回TRUE,否则返回FALSE
if(S.top==0)
return TRUE;
return FALSE;
}
int createMaze(char *filename,Position *startpos,Position *endpos){ //从文件filename读入数据创建迷宫，由参数带回入口位置和出口位置
FILE *fp;
int i,j,rows,cols,temp;
Position start,end;
fp=fopen(filename,"r");
if(!fp){
printf("open file %s error!\n",filename);
return ERROR;
}
if(!feof(fp)){
fscanf(fp,"%d %d",rows,cols); //读入迷宫的行数和列数
fscanf(fp,"%d %d",start.x,start.y); //读入迷宫的入口位置
fscanf(fp,"%d %d",end.x,end.y); //读入迷宫的出口位置
}
for(i=1;i=rows;i++) //读入迷宫数据
for(j=1;j=cols;j++){
fscanf(fp,"%d",temp);
maze[i][j]=48+temp;
}
fclose(fp);
//在迷宫四周加墙
for(i=0,j=0;i=rows+1;i++) maze[i][j]='1';
for(i=0,j=cols+1;i=rows+1;i++) maze[i][j]='1';
for(i=0,j=0;j=cols+1;j++) maze[i][j]='1';
for(i=rows+1,j=0;j=cols+1;j++) maze[i][j]='1';
*startpos=start;
*endpos=end;
return OK;
}
int canPass(Position curpos){
if(maze[curpos.x][curpos.y]=='0')
return TRUE;
return FALSE;
}
void markPos(Position curpos,MarkTag tag){ //为已走过的位置标记
switch(tag){
case YES: maze[curpos.x][curpos.y]='.'; break; //路径标记
case NO: maze[curpos.x][curpos.y]='#'; break; //死胡同标记
}
}
Position nextPos(Position curpos,Direction dir){ //根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标
Position nextpos;
switch(dir){
case RIGHT: nextpos.x=curpos.x; nextpos.y=curpos.y+1; break;
case DOWN: nextpos.x=curpos.x+1; nextpos.y=curpos.y; break;
case LEFT: nextpos.x=curpos.x; nextpos.y=curpos.y-1; break;
case UP: nextpos.x=curpos.x-1; nextpos.y=curpos.y; break;
}
return nextpos;
}
Direction nextDir(Direction dir){
switch(dir){ //按照RIGHT DOWN LEFT UP的次序进行路径探索
case RIGHT: return DOWN;
case DOWN: return LEFT;
case LEFT: return UP;
}
}
/*若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈S中，并返回TRUE，若不存在则返回FALSE*/
int Solve(Stack *S,Position start,Position end){
Position curpos;
SElemType e;
int curstep=1;
if(InitStack(S)==ERROR)
return FALSE;
curpos=start;
do{
if(canPass(curpos)){ //当前位置可以通过
markPos(curpos,YES); //留下足迹
e.order=curstep;
e.seat=curpos;
e.di=RIGHT;
Push(S,e);
if(curpos.x==end.x curpos.y=end.y)
return TRUE; //找到从入口到出口的通道
curpos=nextPos(curpos,RIGHT);
curstep++;
}
else{
if(!Empty(*S)){ //当前位置不能通过
if(Pos(S,e)==ERROR)
return FALSE;
while(e.di==UP !Empty(*S)){ //4个方向都找不到通路，则回溯
curpos=e.seat;
markPos(curpos,NO);
if(Pop(S,e)==ERROR)
return FALSE;
}
if(e.di!=UP){ //4个方向还没有探索完
e.di=nextDir(e.di);
Push(S,e); //换下一个方向探索
curpos=nextPos(e.seat,e.di);
}
}
}while(!Empty(*S));
return FALSE;
}
void main(void){
Position startPos,endPos;
Stack path;
SElemType e;
char *fname="in.txt";
if(createMaze(fname,startPos,endPos)==ERROR) return;
Solve(path,startPos,endPos);
while(!Empty(path)){ //输出出口到入口的路径
Pop(path,e);
printf("(%d,%d)\n",e.seat.x,e.seat.y);
}
}
如何用C语言编写一个迷宫程序？
#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(); }
C语言迷宫找出路问题。帮画个流程图。比如下图
/*
算法
*/
#includestdio.h
#includemalloc.h
#includestdlib.h
#define M 4 //行数
#define N 4 //列数
#define MaxSize 100 //栈最多元素个数
int mg[M+2][N+2]={ //一个迷宫，其四周要加上均为1的外框，1为墙
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,1,1,0,1,1},
{1,0,1,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct migong{
int i; //路径横坐标
int j; //路径纵坐标
int di; //方向
}Stack[MaxSize]; //定义栈
int top=-1; //栈顶指针
void mgpath(){ //路径为:(1,1)-(M,N)从起点1,1走到出口m,n
int i,j,di,find,k;
top++;
Stack[top].i=1;
Stack[top].j=1;
Stack[top].di=-1;
mg[1][1]=-1; //初始结点进栈
while(top-1){ //栈不空时循环
i=Stack[top].i;
j=Stack[top].j;
di=Stack[top].di;
if(i==M j==N){ //找到了出口，输出路径
printf("迷宫出口路径如下:\n");
for(k=0;k=top;k++){
printf("(%d,%d,%d) ",Stack[k].i,Stack[k].j,Stack[k].di);
if((k+1)%5==0) //输出时每5个结点换一行
printf("\n");
}
printf("\n");
break;
}
find=0;
while(di4 find==0){ //找下一个可走结点
di++;
switch(di){
case 0:i=Stack[top].i-1;j=Stack[top].j;break; //上面
case 1:i=Stack[top].i;j=Stack[top].j+1;break; //右边
case 2:i=Stack[top].i+1;j=Stack[top].j;break; //下面
case 3:i=Stack[top].i;j=Stack[top].j-1;break; //左边
}
if(mg[i][j]==0)
find=1;//找到通路
}
if(find == 1){ //找到了下一个可走结点
Stack[top].di=di; //修改原栈顶元素的di值
top++; //下一个可走结点进栈
Stack[top].i=i;
Stack[top].j=j;
Stack[top].di=-1;
mg[i][j]=-1; //避免重复走到该结点
}
else{
mg[Stack[top].i][Stack[top].j]=0; //让该位置变为其他路径的可走结点
if(Stack[top].i==1 Stack[top].j==1)
{
printf("该迷宫问题没有解!\n");
break;
}
top--;
}
}
}
int main(){
printf("\n");
printf(" 迷宫解题问题中心欢迎您 \n");
printf("\n");
printf(" 设计者：么么哒\n");
printf("\n");
printf(" ****************************************************************************** \n");
printf("\n");
mgpath();
return 0;
}
用C语言编写一个迷宫程序，知道出处也行 ~~！
#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");
}
