用c语言实现迷宫求解完美源代码

⽤C语⾔解决迷宫问题#include <stdio.h>#include <stdlib.h>#define ROW 10#define COL 10/*迷宫中位置信息*/typedef struct position{int x;int y;}position;/*在迷宫中的当前位置的信息，也是⼊栈的基本元素*/typedef struct SElem{int di;position seat;}SElem;/*链式栈中节点的定义*/typedef struct position_stack{SElem p;struct position_stack *next;}*Stack_pNode,Stack_Node;void InitStack(Stack_pNode *Link){*Link = NULL;}void push(Stack_pNode *Link,SElem e){Stack_pNode new_SElem = (Stack_pNode)calloc(1,sizeof(Stack_Node));new_SElem->p = e;new_SElem->next = NULL;if (*Link == NULL)*Link = new_SElem;else{new_SElem->next = *Link;*Link = new_SElem;}}int pop(Stack_pNode *Link,SElem *e){if (*Link == NULL)return 0;*e = (*Link)->p;Stack_pNode q = *Link;*Link = (*Link)->next;free(q);return 1;}int top(Stack_pNode Link, SElem *e){if (Link == NULL)return 0;*e = Link->p;return 1;}int empty(Stack_pNode Link){if (Link == NULL)return 1;elsereturn 0;}int reverse(Stack_pNode *Link){Stack_pNode p, q, r;if (*Link == NULL || (*Link)->next == NULL)return 0;r = *Link;p = (*Link)->next;q = NULL;while (p){r->next = q;q = r;r = p;p = p->next;}r->next = q;*Link = r;}void print(Stack_pNode Link){Stack_pNode r = Link;while (r){printf("(%d,%d) -> ",r->p.seat.x,r->p.seat.y);r = r->next;}printf("exit\n");}int curstep = 1;/*纪录当前的⾜迹，填写在探索前进的每⼀步正确的路上*//*迷宫地图。

本程序代码为C语言解决数据结构（严蔚敏）中关于迷宫的问题。

程序不仅实现迷宫路径查找，还实现文字描述路径功能可以直接粘贴到vc6.0中运行【代码如下】# include <stdio.h> # include <malloc.h> # define null 0typedef struct{int (*base)[2];int (*top)[2];int listlen;}sqlist;int topelem[2]; //栈顶元素void creatstack(sqlist *mazepath); //创建一个存储路径的栈void creatmap(int (*mazemap)[10]); //创建迷宫图纸void printmap(int (*mazemap)[10]);void footprint(int x,int y,int k,int (*mazemap)[10]);int position(int x,int y); //判断是否到终点int passroad(int x,int y,int (*mazemap)[10]);void findpath(int (*mazemap)[10],sqlist *mazepath); //在mazemap当中寻找mazepahtvoid printpath(sqlist *mazepath);void roadinwords(sqlist *mazepath); //文字叙述如何走迷宫void push(int x,int y,sqlist *mazepath); //栈操作void pop(sqlist *mazepath);void gettop(sqlist *mazepath);void main(){sqlist mazepath;creatstack(&mazepath); //创建一个存储路径的栈int mazemap[10][10]={1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1};// creatmap(mazemap); //创建迷宫图纸printf("迷宫原图为：\n");printmap(mazemap);findpath(mazemap,&mazepath); //在mazemap当中寻找mazepaht printf("走出迷宫图纸为：\n");printmap(mazemap);printf("走出迷宫文字叙述为：\n");roadinwords(&mazepath);// printpath(&mazepath);}void findpath(int (*mazemap)[10],sqlist *mazepath){int x,y,flag=0,k=0,next; //位置是否可通，flag=0通，1墙，2通但不可走x=1;y=1; //获取初始位置push(x,y,mazepath); //起点位置进栈footprint(x,y,6,mazemap);while(flag==0 && k!=162) //flag==1到达终点,0未到达终点{if(passroad(x,y+1,mazemap)==0)push(x,y+1,mazepath),y=y+1,footprint(x,y,6,mazemap);else if(passroad(x+1,y,mazemap)==0)push(x+1,y,mazepath),x=x+1,footprint(x,y,6,mazemap);else if(passroad(x,y-1,mazemap)==0)push(x,y-1,mazepath),y=y-1,footprint(x,y,6,mazemap);else if(passroad(x-1,y,mazemap)==0)push(x-1,y,mazepath),x=x-1,footprint(x,y,6,mazemap);elsefootprint(x,y,2,mazemap),pop(mazepath),gettop(mazepath),x=topelem[0],y= topelem[1];// printmap(mazemap);k++;flag=position(x,y); //判断是否到达终点// printf("flag==%d\n",flag);}}void creatstack(sqlist *mazepath){mazepath->base=(int (*)[2])malloc(120*sizeof(int (*)[2]));mazepath->top=mazepath->base;mazepath->listlen=120;}void push(int x,int y,sqlist *mazepath){**(mazepath->top)=x;*(*(mazepath->top)+1)=y;mazepath->top++;}void pop(sqlist *mazepath){if(mazepath->top!=mazepath->base)mazepath->top--;}void printmap(int (*mazemap)[10]){int (*p)[10];p=mazemap;int i,j;printf(" \n\n\n");for(i=0;i<10;i++){for(j=0;j<10;j++){if(j==0)printf(" ");if(*(*(p+i)+j)==0)printf("▇");else if(*(*(p+i)+j)==1)printf("□");else if(*(*(p+i)+j)==6)printf("★");elseprintf("▇");if(j==9)printf("\n");}}printf("\n\n");}void printpath(sqlist *mazepath){int (*p)[2];p=mazepath->base;while(p!=mazepath->top){printf("x=%d,y=%d\n",**p,*(*p+1));p++;}}void gettop(sqlist *mazepath){int (*p)[2];int (*q)[2];p=mazepath->base;while(p!=mazepath->top){q=p;p++;}topelem[0]=**q;topelem[1]=*(*q+1);}void footprint(int x,int y,int k,int (*mazemap)[10]){if(x<10 && y<10)*(*(mazemap+x)+y)=k;}int position(int x,int y){int flag;if(x==8 && y==8)flag=1;elseflag=0;return(flag);}int passroad(int x,int y,int (*mazemap)[10]) {int num=1;if(x<10 && y<10)num=*(*(mazemap+x)+y);return(num);}void roadinwords(sqlist *mazepath){int x=1,y=1,i=0;int (*p)[2];p=mazepath->base;p++;while(p!=mazepath->top){if(x==**p && y+1==*(*p+1))printf("向右走→→"),x=**p,y=*(*p+1);else if(x+1==**p && y==*(*p+1))printf("向下走→→"),x=**p,y=*(*p+1);else if(x==**p && y-1==*(*p+1))printf("向左走→→"),x=**p,y=*(*p+1);else if(x-1==**p && y==*(*p+1))printf("向上走→→"),x=**p,y=*(*p+1);i++;if(i%3==0)printf("\n");p++;}printf("\n");}。

#include"stdio.h"#include"stdlib.h"#define M1 11#define N1 11 /*M1*N1为加上围墙后的迷宫大小*/#define MAX 100 /*定义栈的最大长度*/int M=M1-2;int N=N1-2; /*M*N为原迷宫大小*/typedef struct /*定义栈元素的类型*/{int x,y,dir;}elemtype;typedef struct /*定义顺序栈*/{elemtype stack[MAX];int top;}P;struct moved /*定义方向位移数组的类型*/{int dx;int dy;};void Newmg(int mg[M1][N1]) /*迷宫的初始化*/{int i,j,num;printf("迷宫：\n");for (i=1;i<=M;i++){for (j=1;j<=N;j++){num=(800*(i+j)+1500)%327; /*根据N和M值伪随机产生迷宫*/if((num<150)&&(i!=M||j!=N))mg[i][j]=1;elsemg[i][j]=0;printf("%3d",mg[i][j]);} /*输出迷宫*/printf("\n");}printf("\n");for(i=0;i<=M+1;i++) /*设置迷宫的围墙*/{mg[i][0]=1;mg[i][N+1]=1;}for(j=0;j<=N+1;j++)mg[0][j]=1;mg[N+1][j]=1;}}void Newmove(struct moved move[8]) /*定义存储坐标变量的方向位移*/ {move[0].dx=0;move[0].dy=1; /*寻找方向依次为:东，东南，南，move[1].dx=1;move[1].dy=1; 西南，西，西北，北，东北*/ move[2].dx=1;move[2].dy=0;move[3].dx=1;move[3].dy=-1;move[4].dx=0;move[4].dy=-1;move[5].dx=-1;move[5].dy=-1;move[6].dx=-1;move[6].dy=0;move[7].dx=-1;move[7].dy=1;}void Newstack(P *s) /*初始化栈*/{s->top=-1;}int RuZhan(P *s ,elemtype x) /*将数据元素x压入指针s所指的栈中*/ {if (s->top==MAX-1)return (0); /*如栈满，即压栈失败，则返回0*/ else{s->stack[++s->top]=x;return(1); /*压栈成功，则返回1*/}}elemtype ChuZhan(P *s) /*栈顶元素出栈*/{elemtype elem;if (s->top<0) /*如果栈空，返回空值*/{elem.x=NULL;elem.y=NULL;elem.dir=NULL;return(elem);}elses->top--;return(s->stack[s->top+1]); /*如果栈非空，返回栈顶元素*/}}void Search(int mg[M1][N1],struct moved move[8],P *s){ /*寻找迷宫的通路*/int i,j,dir,x,y,k;elemtype elem;i=1;j=1;dir=0;mg[1][1]=-1; /*设置（1，1）为入口处*/do{x=i+move[dir].dx; /*寻找下一步可行的到达点的坐标*/y=j+move[dir].dy;if(mg[x][y]==0){elem.x=i;elem.y=j;elem.dir=dir;k=RuZhan(s,elem); /*如果可通过，将此点数据压栈*/if(k==0)printf("栈长度太短\n"); /*如果入栈操作返回0，说明栈容量不够*/i=x;j=y;dir=0;mg[x][y]=-1;}else if(dir<7)dir++;else /*如果八个方向都不可行，就退回一步*/ {elem=ChuZhan(s);if (elem.x!=NULL){i=elem.x;j=elem.y;dir=elem.dir+1;}}}while (!((s->top==-1)&&(dir>=7)||(x==M)&&(y==N)));/*循环，直到入口处或出口处为止*/if(s->top==-1) /*如果最终是入口处，则迷宫无通路*/printf("此迷宫无通路\n");else{elem.x=x;elem.y=y;elem.dir=dir;k=RuZhan(s,elem); /*将最后出口的坐标压入栈中*/printf("迷宫通路：\n");printf (" 入口->");i=0;while (i<=s->top){printf("(%d,%d)->",s->stack[i].x,s->stack[i].y); /*显示迷宫通路*/ if(i!=s->top)if((i+1)%4==0)printf("\n");i++;}printf ("出口\n");}}void main() /*寻找迷宫通路程序*/{P *s;int mg[M1][N1];struct moved move[8];Newmg (mg); /*调用函数初始化迷宫*/s=(P*)malloc(sizeof(P));Newstack(s); /*调用函数初始化栈*/Newmove(move); /*调用函数初始化位移数组*/ Search (mg,move,s); /*调用函数寻找迷宫通路*/}。

迷宫求解完整代码3.本程序包括三个模块1) 主程序模块:void main(){初始化;do{接受命令;处理命令;}while(命令!=”退出”);}2) 栈模块------实现栈的抽象数据类型 3)迷宫模块----实现迷宫抽象数据类型各个模块之间的调用关系如下:主程序模块->迷宫模块 ->栈模块三( 详细设计1. 坐标位置类型typedef struct PosType //定义坐标 {int x; //当前横坐标int y; //当前纵坐标 }PosType;2.迷宫类型int Maze[][];//迷宫存放在一个数字型数组中int MazePath(int maze[N][N],PosType start,PosType end,LinkStack&stack,int n1,int n2)//求解迷宫maze中，从入口Start到出口end的一条路径{stack=NULL;SElemType e;PosType curpos;InitStack(stack);//初始化stackcurpos.x=start.x; //设定当前位置为入口位置curpos.y=start.y;int curstep=1; //探索第一步do{if(Pass(curpos,maze,n1,n2)==1)//当前位置可通{FootPrint(curpos,maze); //留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e); //加入路径，入栈if(curpos.x==end.x&&curpos.y==end.y) //到达出口位置return 1;elseNextPos(curpos,1); //探索下一步curstep++;}//ifelse //当前位置不能通过{if(!StackEmpty(stack)){Pop(stack,e);while(e.di==4&&!StackEmpty(stack)){MarkPrint(e.seat,maze);//留下不能通过的标记，并退回一步Pop(stack,e);}//while}if(e.di<4) //换下一个方向探索{e.di++;Push(stack,e);NextPos(e.seat,e.di); //设当前位置是该新方向上的相邻块，1代表向右，2代表向下，3代表向左，4代表向上。

c语言走迷宫代码以下是一个简单的 C 语言走迷宫代码示例，使用了递归算法: ```c#include <stdio.h>#include <stdlib.h>int main() {int size, row, col, choice, i, j;maze[0][0] = "*";maze[1][0] = "O";maze[0][1] = "O";maze[1][1] = "*";size = 2;row = 2;col = 2;while (1) {printf("Enter row: ");scanf("%d", &row);printf("Enter col: ");scanf("%d", &col);if (row < 0 || row > size || col < 0 || col > size) { printf("Invalid row or col. Try again.");}if (maze[row][col] != "*") {printf("Current cell is free. Try again. ");continue;}maze[row][col] = "X";printf("Enter a choice (1-6): ");scanf("%d", &choice);switch (choice) {case 1:row++;col = 0;break;case 2:row--;col = 0;break;case 3:col++;break;col--;break;case 5:row--;col = 1;break;case 6:row++;col = 1;break;default:printf("Invalid choice. Try again. ");continue;}}printf(" maze: ");for (i = 0; i < size * size; i++) { for (j = 0; j < size; j++) {if (maze[i][j] == "*")printf("*");elseprintf("%c", maze[i][j]);}printf("");}return 0;}```该程序首先初始化了一个 2x2 的迷宫，其中 `maze[0][0]` 和`maze[1][0]` 分别标记为 `"O"` 和 `"*"`,其他地方都为空。

#include <graphics.h>#include <stdlib.h>#include <bios.h>/*定义几个功能按键*/#define ESC 0x11b /*强行退出游戏*/#define UP 0x4800 /*上下左右四个按键移动小人*/#define DOWN 0x5000#define LEFT 0x4b00#define RIGHT 0x4d00int a[50][50]={0}; /* 存放地图信息的数组0：不可走的障碍物1：可以走的路*/ int qdx=1,qdy=1,zdx=20,zdy=20; /* 起点和终点的坐标*/int renx,reny; /* 小人坐标*/int d=20; /* 小格子的间距*/int kk=0,rr=2;main(){int i,j,m=30,n=16,d=20,k;int gdriver = DETECT, gmode;randtu(200);renx=qdx,reny=qdy;registerbgidriver(gdriver);initgraph(&gdriver, &gmode, "c:\\turboc2");redraw();while(1) /* 反复从键盘获得程序需要的按键*/{if(bioskey(1)) /* 判断是否有按键*/{k=bioskey(0); /* 将按键存入变量k */switch(k) /* 对按键进行分情况处理*/{case ESC: /* ESC键退出*/printf("%d times\n",kk);exit(0); break;case UP: /* UP键向上移动光标*/if(a[renx][reny-1]==1){reny-=1;redraw();}break;case DOWN: /* DOWN键向下移动光标*/if(a[renx][reny+1]==1){reny+=1;redraw();}break;case LEFT: /* LEFT键向左移动光标*/if(a[renx-1][reny]==1){renx-=1;redraw();}break;case RIGHT: /* RIGHT键向右移动光标*/if(a[renx+1][reny]==1){renx+=1;redraw();}break;}}}getch();closegraph();}/*redraw重画函数在用户有操作后，重画游戏画面*/redraw(){int i,j;for(i=qdx;i<=zdx;i++)for(j=qdy;j<=zdy;j++){if(i<renx+rr && i>renx-rr && j<reny+rr && j>reny-rr)if(a[i][j]==0) geziza(i*d,j*d);else gezilu(i*d,j*d);else gezibk(i*d,j*d);}drawren(renx*d,reny*d);}/*随机地图（randlei）函数用于随机生成地图*/randtu(int num){int i,j,xx,yy,sum,t,m,n;srand(time(NULL));loop: sum=0;m=zdy-qdy+1;n=zdx-qdx+1;a[qdx][qdy]=1;a[zdx][zdy]=1;do{t=random(m*n);xx=t/m+1;yy=t%m+1;if(a[xx][yy]==0){a[xx][yy]=1;sum++;}}while(sum<num);if(ok()) return;for(i=0;i<50;i++)for(j=0;j<50;j++)a[i][j]=0;kk++;goto loop;}ok(){ int b[50][50]={0};b[qdx][qdy]=1;tansuo(qdx,qdy,b);return(b[zdx][zdy]);}tansuo(int x,int y,int *b[50][50]) /* 如果当前格子为空白无雷情况，向周围探索相类似的情况，并打开周围的数字*/{if(a[x][y-1]==1 && b[x][y-1]==0){b[x][y-1]=1;tansuo(x,y-1,b);}if(a[x+1][y]==1 && b[x+1][y]==0){b[x+1][y]=1;tansuo(x+1,y,b);}if(a[x-1][y]==1 && b[x-1][y]==0){b[x-1][y]=1;tansuo(x-1,y,b);}if(a[x][y+1]==1 && b[x][y+1]==0){b[x][y+1]=1;tansuo(x,y+1,b);}}/*绘制障碍物小格子（geziza）int x : 格子左上角点横坐标int y ：格子左上角点纵坐标*/geziza(int x,int y){int i;setcolor(8);rectangle(x,y,x+d,y+d);setcolor(RED);setfillstyle(2,RED);bar(x+1,y+1,x+d-1,y+d-1);/* 设置深灰色为格子边框*/ }/*绘制障碍物小格子（geziza）int x : 格子左上角点横坐标int y ：格子左上角点纵坐标*/gezibk(int x,int y){int i;setcolor(8);rectangle(x,y,x+d,y+d);setcolor(BLUE);setfillstyle(2,BLUE);bar(x+1,y+1,x+d-1,y+d-1);/* 设置深灰色为格子边框*/}gezilu(int x,int y){int i;setcolor(8); /* 设置深灰色为格子边框*/ rectangle(x,y,x+d,y+d);setcolor(BLUE);setfillstyle(8,BLUE);bar(x+1,y+1,x+d-1,y+d-1);}/*画小人（drawren）函数用于绘制给定坐标位置的小人小人画在格子的正中心格子背景色为红色int x : 所在格子左上角点横坐标int y ：所在格子左上角点纵坐标*/drawren(int x,int y){int i;setcolor(8); /* 设置深灰色为格子边框*/ rectangle(x,y,x+d,y+d);setcolor(YELLOW);for(i=1;i<d/2-3;i++)circle(x+d/2,y+d/2,i);}/*over（over）函数用于判断游戏是否结束*/over(){}。

c语言迷宫代码C语言迷宫代码是指用C语言编写的程序，用于生成和解决迷宫问题的算法。

迷宫通常由一个矩形网格组成，其中包含墙壁和通道。

目标是找到从迷宫的起点到终点的路径，同时避开墙壁。

下面是一个简单的示例代码，用于生成迷宫：```c#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define ROWS 10#define COLS 10typedef struct {int x;int y;} Point;void generateMaze(int maze[ROWS][COLS]) {for (int i = 0; i < ROWS; i++) {for (int j = 0; j < COLS; j++) {if (i % 2 == 0 || j % 2 == 0) { maze[i][j] = 1; // 墙壁} else {maze[i][j] = 0; // 通道}}}}void printMaze(int maze[ROWS][COLS]) {for (int i = 0; i < ROWS; i++) {for (int j = 0; j < COLS; j++) {printf('%d ', maze[i][j]);}printf('');}}int main() {int maze[ROWS][COLS];generateMaze(maze);printMaze(maze);return 0;}```在上面的代码中，我们使用一个二维数组来表示迷宫。

数组中的值为1表示墙壁，值为0表示通道。

使用generateMaze函数，我们将迷宫的墙壁和通道初始化为适当的值。

然后使用printMaze函数打印迷宫。

通过运行上面的代码，我们可以得到一个简单的迷宫的表示：```1 1 1 1 1 1 1 1 1 11 0 1 0 1 0 1 0 1 11 1 1 1 1 1 1 1 1 11 0 1 0 1 0 1 0 1 11 1 1 1 1 1 1 1 1 11 0 1 0 1 0 1 0 1 11 1 1 1 1 1 1 1 1 11 0 1 0 1 0 1 0 1 11 1 1 1 1 1 1 1 1 11 0 1 0 1 0 1 0 1 1```当然，上述代码只是生成了一个简单的迷宫，还没有解决迷宫问题。

迷宫非递归求解(c语言)源代码.txt51自信是永不枯竭的源泉，自信是奔腾不息的波涛，自信是急流奋进的渠道，自信是真正的成功之母。

#include <stdio.h>#include <stdlib.h>#define MaxSize 100#define StackIncrement 10struct Seat{ //定义坐标结构体int x;int y;};typedef struct { //定义入栈信息元素类型int ord;Seat seat;int di;}SElemType;struct Stack{ //定义栈元素类型SElemType *base;SElemType *top;int StackLength;};Stack S;bool Map[10][10]={{0},{0,1,1,0,1,1,1,0,1,0},{0,1,1,0,1,1,1,0,1,0},{0,1,1,1,1,0,0,1,1,0},{0,1,0,0,0,1,1,1,1,0},{0,1,1,1,0,1,1,1,1,0},{0,1,0,1,1,1,0,1,1,0},{0,1,0,0,0,1,0,0,1,0},{0,0,1,1,1,1,1,1,1,0},{0}};bool is_through[10][10]={0};bool InitStack(Stack &S){ //构建一个栈S.base=S.top=(SElemType*)malloc(MaxSize*sizeof(SElemType));if(!S.base)return false;S.StackLength=MaxSize;return true;}bool Push(Stack &S,SElemType e){ // 将信息e入栈if((S.top-S.base)/sizeof(SElemType)==S.StackLength){S.base=(SElemType*)realloc(S.base,(S.StackLength+StackIncrement)*sizeof(SEle mType));S.top=S.base+S.StackLength;S.StackLength += StackIncrement;}S.top->di=e.di; S.top->ord=e.ord; S.top->seat.x=e.seat.x; S.top->seat.y=e.seat.y;S.top++;return true;}bool Pop(Stack &S,SElemType &e){ //将栈顶元素取出，赋值给eif(S.base==S.top)return false;S.top--;e.di=S.top->di; e.ord=S.top->ord; e.seat.x=S.top->seat.x;e.seat.y=S.top->seat.y;return true;}bool StackEmpty(Stack s){ //判断栈是否为空return !(s.top-s.base);}bool Pass(Seat s){ //判断当前位置是否通return Map[s.x][s.y];}bool FootPrint(Seat s){ // 在此位置留下标记，表示已经经过is_through[s.x][s.y]=true;return true;}Seat NextPos(Seat s,int i){ // 将当前位置指向逻辑上的下个位置，指向的方向由i确定Seat ss;if(i==1){ss.x=s.x+1; ss.y=s.y;}elseif(i==2){ss.x=s.x; ss.y=s.y+1;}elseif(i==3){ss.x=s.x-1; ss.y=s.y;}else{ss.x=s.x; ss.y=s.y+1;}return ss;}bool MazePath(Seat start,Seat end){InitStack(S); //创建栈并且初始化Seat curpos; curpos.x=start.x; curpos.y=start.y; //设定当前位置为入口地址int curstep=1; // 探索第一步do{if(Pass(curpos)&&!is_through[curpos.x][curpos.y]){ // 当前位置通且没有来过FootPrint(curpos); // 留下痕迹SElemType e; // 构建入栈信息e.di=1; e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y;Push(S,e); // 加入路径if((curpos.x==end.x)&&(curpos.y==end.y)) // 到达终点return true;curpos=NextPos(curpos,1); // 探索下一步curstep++;}else{ // 当前位置不通，将前面一个位置取出，改由其他方向在判断SElemType e;if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){FootPrint(e.seat); Pop(S,e); // 如果这个位置的其他四个方向都不满足，表示这个位置不可取，取出栈并且留下标识}if(e.di<4){ // 如果其他方向还没有探索完，继续探索下一个方向e.di++; Push(S,e);curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));return false;}int main(){int i,j;Seat sta,end;sta.x=1; sta.y=1; end.x=8; end.y=8;MazePath(sta,end);SElemType *b=S.base;printf("迷宫地图为(1表示通，0表示不通):\n");for(i=0;i<10;i++){for(j=0;j<10;j++)printf("%d ",Map[i][j]);printf("\n");}printf("迷宫路径为:");while(b!=S.top){printf("(%d,%d) -> ",b->seat.x,b->seat.y);++b;}printf("出口\n");scanf("%d",i);return 0;}。

用c语言实现迷宫求解完美源代码#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define UNDERFLOW -2typedef int Status;//-----栈开始-----typedef struct{//迷宫中r行c列的位置int r;int c;}PostType;//坐标位置类型typedef struct{int ord;// 当前位置在路径上的序号PostType seat;// 当前坐标int di;// 从此通块走向下一通块的“方向”}SElemType;// 栈的元素类型//定义链式栈的存储结构struct LNode{SElemType data;//数据域struct LNode *next;//指针域};struct LStack{struct LNode *top;//栈顶指针};Status InitStack(LStack &s)//操作结果：构造一个空栈S {struct LNode *p;p=(LNode *)malloc(sizeof(LNode));if(!p){printf("分配失败，退出程序");exit(ERROR);}s.top=p;p->next=NULL;return OK;}Status StackEmpty(LStack s)//若栈s为空栈，则返回TRUE，否则FALSE{if(s.top->next==NULL) return TRUE;return FALSE;}Status Push(LStack &s,SElemType e)//插入元素e成为新的栈顶元素{struct LNode *p;p=(LNode *)malloc(sizeof(LNode));if(!p) exit(OVERFLOW);s.top->data=e;p->next=s.top;s.top=p;return OK;}Status Pop(LStack &s,SElemType &e)//删除s的栈顶元素，并且用e返回其值{struct LNode *p;if(!(s.top->next)) exit(UNDERFLOW);p=s.top;s.top=p->next;e=s.top->data;free(p);return OK;}Status DestroyStack(LStack &s)//操作结果：栈s被销毁{struct LNode *p;p=s.top;while(p){s.top=p->next;free(p);p=s.top;}return OK;}//-----栈结束------//-----迷宫开始-------#define MAXLEN 10// 迷宫包括外墙最大行列数typedef struct{int r;int c;char adr[MAXLEN][MAXLEN];// 可取' ''*' '@' '#'}MazeType;// 迷宫类型Status InitMaze(MazeType&maze){// 初始化迷宫，成功返回TRUE，否则返回FALSE int m,n,i,j;printf("输入迷宫行数和列数（包括了外墙）: ");scanf("%d%d",&maze.r,&maze.c); // 输入迷宫行数和列数for(i=0;i<=maze.c+1;i++){// 迷宫行外墙maze.adr[0][i]='#';maze.adr[maze.r+1][i]='#';}//forfor(i=0;i<=maze.r+1;i++){// 迷宫列外墙maze.adr[i][0]='#';maze.adr[i][maze.c+1]='#';}for(i=1;i<=maze.r;i++)for(j=1;j<=maze.c;j++)maze.adr[i][j]=' ';// 初始化迷宫printf("输入障碍的坐标((-1 -1)结束): ");scanf("%d%d",&m,&n);// 接收障碍的坐标while(m!=-1){if(m>maze.r || n>maze.c)// 越界exit(ERROR);maze.adr[m][n]='#';// 迷宫障碍用#标记printf("输入障碍的坐标((-1,-1)结束): ");scanf("%d%d",&m,&n);}//whilereturn OK;}//InitMazeStatus Pass(MazeType maze,PostType curpos){// 当前位置可同则返回TURE,否则返回FALSEif(maze.adr[curpos.r][curpos.c]==' ')// 可通return TRUE;elsereturn FALSE;}//PassStatus FootPrint(MazeType &maze,PostType curpos) {// 若走过并且可通，则返回TRUE,否则返回FALSE maze.adr[curpos.r][curpos.c]='*';//"*"表示可通return OK;}//FootPrintPostType NextPos(PostType &curpos,int i){// 指示并返回下一位置的坐标PostType cpos;cpos=curpos;switch(i){//1.2.3.4 分别表示东南西北方向case 1 : cpos.c+=1; break;case 2 : cpos.r+=1; break;case 3 : cpos.c-=1; break;case 4 : cpos.r-=1; break;default: exit(ERROR);}return cpos;}//NextposStatus MarkPrint(MazeType &maze,PostType curpos) {// 曾走过，但不是通路标记，并返回OKmaze.adr[curpos.r][curpos.c]='@';//"@" 表示曾走过但不通return OK;}//MarkPrintStatus MazePath(MazeType &maze,PostType start,PostType end){// 若迷宫maze存在通路，则求出一条同路放在栈中，并返回TRUE，否则返回FALSE struct LStack S;PostType curpos;int curstep;// 当前序号，1,2,3,4分别表示东南西北方向SElemType e;InitStack(S);curpos=start; //设置"当前位置"为"入口位置"curstep=1;// 探索第一位printf("以三元组形式表示迷宫路径：\n");do{if(Pass(maze,curpos)){// 当前位置可以通过FootPrint(maze,curpos);// 留下足迹e.ord=curstep;e.seat=curpos;e.di=1;printf("%d %d %d-->",e.seat.r,e.seat.c,e.di);Push(S,e);// 加入路径if(curpos.r==end.r&&curpos.c==end.c)if(!DestroyStack(S))// 销毁失败exit(OVERFLOW);elsereturn TRUE; // 到达出口else{curpos=NextPos(curpos,1);// 下一位置是当前位置的东邻curstep++;// 探索下一步}//else}//ifelse{// 当前位置不通时if(!StackEmpty(S)){Pop(S,e);while(e.di==4&& !StackEmpty(S)){MarkPrint(maze,e.seat);Pop(S,e);// 留下不能通过的标记，并退一步}//whileif(e.di < 4){e.di++;// 换一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);// 设定当前位置是该方向上的相邻printf("%d %d %d-->",e.seat.r,e.seat.c,e.di);}//if}//if}//else}while(!StackEmpty(S));if(!DestroyStack(S))// 销毁栈exit(OVERFLOW);elsereturn FALSE;}//MazePathvoid PrintMaze(MazeType &maze){// 将标记路径信息的迷宫输出到终端int i,j;printf("\n输出迷宫(*表示通路):\n\n");printf("");for(i=0;i<=maze.r+1;i++)// 打印列数名printf("%4d",i);printf("\n\n");for(i=0;i<=maze.r+1;i++){printf("%2d",i);// 打印行名for(j=0;j<=maze.c+1;j++)printf("%4c",maze.adr[i][j]);// 输出迷宫当前位置的标记printf("\n\n");}}//PrintMazeint main(){// 主函数MazeType maze;PostType start,end;char cmd;do{printf("-------创建迷宫--------\n");if(!InitMaze(maze)){printf("Initialization errors\n");exit(OVERFLOW);// 初始化失败}do{// 输入迷宫入口坐标printf("\n输入迷宫入口坐标: ");scanf("%d%d",&start.r,&start.c);if(start.r>maze.r ||start.c>maze.c){printf("\nBeyond the maze\n"); continue;}}while(start.r>maze.r ||start.c>maze.c);do{// 输入迷宫出口坐标printf("\n输入迷宫出口坐标: ");scanf("%d%d",&end.r,&end.c);if(end.r>maze.r ||end.c>maze.c){printf("\nBeyond the maze\n"); continue;}}while(end.r>maze.r ||end.c>maze.c);if(!MazePath(maze,start,end))//迷宫求解printf("\nNo path from entranceto exit!\n"); elsePrintMaze(maze);// 打印路径printf("\n需要继续创建新的迷宫吗?(y/n): "); scanf("%s",&cmd);}while(cmd=='y' || cmd=='Y');}。

#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10typedef struct{int r;int c;}PosType;//通道块坐标typedef struct {int ord;//通道块在路径上的序号PosType seat;//通道块的坐标位置int di;//下一个探索的方向}SelemType;typedef struct {int r;int c;char adr[10][10];}MazeType;//迷宫行列，内容typedef struct {SelemType * base;SelemType * top;int stacksize;}SqStack;void InitStack(SqStack &S){S.base=(SelemType*)malloc(STACK_INIT_SIZE * sizeof(SelemType));if(!S.base) exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}void 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(0);S.top=S.base+S.stacksize;//溢出重新定位S.stacksize+=STACKINCREMENT;}*S.top++=e;}void Pop(SqStack &S,SelemType &e){if(S.top==S.base) return;e=*--S.top;}void InitMaze(MazeType &maze){int i,j;maze.r=8;maze.c=8;for(i=0;i<10;i++){maze.adr[0][i]='#';maze.adr[9][i]='#';}for(i=0;i<10;i++){maze.adr[i][0]='#';maze.adr[i][9]='#';}for(i=1;i<9;i++)for(j=1;j<9;j++)maze.adr[i][j]='1';maze.adr[1][3]='#'; maze.adr[1][7]='#';maze.adr[2][3]='#'; maze.adr[2][7]='#';maze.adr[3][5]='#'; maze.adr[3][6]='#';maze.adr[4][2]='#'; maze.adr[4][3]='#';maze.adr[4][4]='#';maze.adr[5][4]='#';maze.adr[6][2]='#'; maze.adr[6][6]='#';maze.adr[7][2]='#'; maze.adr[7][3]='#'; maze.adr[7][4]='#'; maze.adr[7][6]='#';maze.adr[7][7]='#';maze.adr[8][1]='#';}int Pass(MazeType &maze,PosType &curpos){if(maze.adr[curpos.r][curpos.c]=='1')return 1;elsereturn 0;}void FootPrint(MazeType &maze,PosType curpos){maze.adr[curpos.r][curpos.c]='*';//已经走过的标记}PosType NextPos(PosType curpos,int i){PosType nextpos;nextpos=curpos;switch(i){case 1:nextpos.c+=1;break;case 2:nextpos.r+=1;break;case 3:nextpos.c-=1;break;case 4:nextpos.r-=1;break;default:printf("探寻方向错误!");}return nextpos;}void MarkPrint(MazeType &maze,PosType curpos){maze.adr[curpos.r][curpos.c]='@';//不通的标识}int StackEmpty(SqStack &S){if(S.base==S.top)return 1;elsereturn 0;}void MazePath(MazeType &maze,PosType start,PosType end) {SelemType e;SqStack S;InitStack(S);PosType curpos;int curstep;curpos=start;curstep=1;do{if(Pass(maze,curpos)){FootPrint(maze,curpos);//留下走过足迹*e.ord=curstep;e.seat=curpos;e.di=1;Push(S,e);//压入栈路径if(curpos.r==end.r&&curpos.c==end.c) return;curpos=NextPos(curpos,1);//探索下一步curstep++;}//ifelse{//当前位置不能通过if(!StackEmpty(S)){Pop(S,e);//top指针退后一下，指向上一步while(e.di==4&&!StackEmpty(S)){MarkPrint(maze,e.seat);//如果此步上下左右都探索过了且栈不为空留下不通过且返回一步Pop(S,e);}//while,用while是可以连续返回if(e.di<4){e.di++;Push(S,e);//换下一个方向探索curpos=NextPos(e.seat,e.di);//探索下一位置块}//if}//if}//else}while(!StackEmpty(S));}//mazepathvoid PrintMaze(MazeType &maze){int i,j;for(i=0;i<10;i++)printf("%4d",i);//输出行printf("\n\n");for(i=0;i<10;i++){printf("%2d",i);//输出列for(j=0;j<10;j++)printf("%4c",maze.adr[i][j]);printf("\n\n");}}void main(){MazeType maze;PosType start,end;InitMaze(maze);start.r=1; start.c=1;end.r=8; end.c=8;PrintMaze(maze);MazePath(maze,start,end);PrintMaze(maze);}。

//其中0表示路，1表示墙，-1表示已走过//迷宫问题广度优先算法# include<stdio.h># include<stdlib.h>typedef struct squeue{int x;int y;int pre;}squeue;squeue Q[100]; //队列用于存放迷宫通路int qe,qh; //队列指针int map[8][8]={{0,0,0,0,0,0,0,0},{0,1,1,1,1,0,1,0},{0,0,0,0,1,0,1,0},{0,1,0,0,0,0,1,0},{0,1,0,1,1,0,1,0},{0,1,0,0,0,0,1,1},{0,1,0,0,1,0,0,0},{0,1,1,1,1,1,1,0}}; //存放迷宫地图int fx[5]={0,1,-1,0,0},fy[5]={0,0,0,-1,1}; //模拟四个运动方向int check(int i,int j) //检查当前位置是否合适{int flag=1;if(i<0||i>7) //检查行是否越界flag=0;if(j<0||j>7) //检查列是否越界flag=0;if(map[i][j]==1||map[i][j]==-1) //当前位置是否可行flag=0;return flag;}void print() //输出迷宫路径{ int sum=1;printf("\n所求密宫路径为:\n");printf("(%d,%d)",Q[qe].x,Q[qe].y);while(Q[qe].pre!=0){qe=Q[qe].pre;printf("<--(%d,%d)",Q[qe].x,Q[qe].y);sum++;if(sum%5==0)printf("\n");}// printf("<--(%d,%d)\n",Q[qe].x,Q[qe].y);}int search() //走迷宫{int i,j,k;qh=0;qe=1;map[0][0]=-1; //入口入队列,并将其标志变量致零Q[1].pre=0;Q[1].x=0;Q[1].y=0;while(qh!=qe){qh++; //队首元素出队列for(k=1;k<=4;k++) //搜索前后左右四个方向{i=Q[qh].x+fx[k];j=Q[qh].y+fy[k];if(check(i,j)==1){qe++; //入队列，并改变其标志变量Q[qe].x=i;Q[qe].y=j;Q[qe].pre=qh;map[i][j]=-1;if(Q[qe].x==7&&Q[qe].y==7) //若到迷宫出口，则输出路径{print();return 0;}}}}printf("NO Way!\n");return 0;}void main(){int i,j;printf("迷宫图为:");for(i=0;i<=7;i++) //输出原迷宫图{printf("\n");for(j=0;j<=7;j++)printf("%d ",map[i][j]);}printf("\n");search();}。

#include<stdio.h>#include<stdlib.h>#include"Status.h"typedef struct{int x;int y;}posType;typedef struct{posType pos;int dirc;}SElemType;#include"SqStack.h"#define Row 12#define Col 12posType nextPos(posType curPos,int d){posType pos;switch(d){case 1: pos.x=curPos.x;pos.y=curPos.y+1;break;case 2: pos.x=curPos.x+1;pos.y=curPos.y;break;case 3: pos.x=curPos.x;pos.y=curPos.y-1;break;case 4: pos.x=curPos.x-1;pos.y=curPos.y;break;}return pos;}Status canGo(posType pos,int M[Row][Col]){if(M[pos.x][pos.y]==0) return TRUE;else return FALSE;}Status Maze(int M[Row][Col],posType start,posType end){ SqStack S;SElemType e;posType curPos;int d,step;InitSqStack(&S,100);curPos=start;d=4;do{if(canGo(curPos,M)){M[curPos.x][curPos.y]=2;e.pos=curPos;e.dirc=d;Push(&S,e);if(curPos.x==end.x&&curPos.y==end.y) break;d=1;curPos=nextPos(curPos,d);}else if(d<4){d++;getTop(S,&e);curPos=nextPos(e.pos,d);}else if(!stackIsEmpty(S)){Pop(&S,&e);d=e.dirc;curPos=e.pos;}}while(!stackIsEmpty(S));if(!stackIsEmpty(S)){Pop(&S,&e);M[e.pos.x][e.pos.y]='e';d=e.dirc;for(step=stackLength(S);step>0;step--){Pop(&S,&e);switch(d){case 1: M[e.pos.x][e.pos.y]=26;break;case 2: M[e.pos.x][e.pos.y]=25;break;case 3: M[e.pos.x][e.pos.y]=27;break;case 4: M[e.pos.x][e.pos.y]=24;break;}d=e.dirc;}M[start.x][start.y]='s';return TRUE;}else return FALSE;}void printMaze(int M[Row][Col],posType start,posType end){int i,j;printf("迷宫:入口(%d,%d),出口(%d,%d)\n",start.x,start.y,end.x,end.y); printf("\t%3c",' ');for(i=0;i<Col;i++)printf("%2d ",i);printf("\n");for(i=0;i<Row;i++){printf("\t%2d",i);for(j=0;j<Col;j++){if(M[i][j]==1)printf("|||");else if(M[i][j]==0)printf(" ");else if(M[i][j]==2)printf(" = ");else printf(" %c",M[i][j]);}printf("\n");}printf("\n");}int main(){int M[Row][Col]={{1,1,1,1,1,1,1,1,1,1,1,1},{1,0,0,0,1,1,0,1,1,1,0,1},{1,0,1,0,0,1,0,0,1,0,0,1},{1,0,1,1,0,0,0,1,1,0,1,1},{1,0,0,1,0,1,0,0,0,0,0,1},{1,1,0,1,0,1,1,0,1,0,1,1},{1,0,0,1,0,0,0,0,1,1,1,1},{1,0,1,0,1,1,1,1,0,0,1,1},{1,0,0,0,0,1,1,0,0,0,1,1},{1,0,1,0,1,0,0,0,1,0,0,1},{1,0,0,0,0,0,1,0,0,1,0,1},{1,1,1,1,1,1,1,1,1,1,1,1} };posType start,end;start.x=1;start.y=1;end.x=10;end.y=10;printMaze(M,start,end);if(Maze(M,start,end)){printf("找到可行路径:\n");printMaze(M,start,end);}else printf("无可行路径！\n");system("pause");return 0;}。