下载文档原格式
⽤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");}。
c语言随机生成迷宫算法迷宫是一种很有趣的游戏，它可以让人们在寻找出路的过程中培养思考能力和耐心。
在许多计算机游戏中，迷宫也是一个常见的题材。
那么，如何用C语言自动生成一个迷宫呢？下面就来详细介绍一下。
第一步，确定迷宫大小首先要确定迷宫的大小，也就是行和列的数量。
这可以通过用户输入来实现，也可以直接在程序中定义。
第二步，初始化迷宫在程序中，我们通常用一个二维数组来表示迷宫，数组元素的值表示对应的格子状态，0表示可通过，1表示不可通过。
因此，我们需要在程序中初始化迷宫，将所有的格子都标记为1，表示不可通过。
第三步，生成迷宫路径接下来，我们需要随机生成一个迷宫路径。
随机生成迷宫路径的方法有很多种，这里介绍一种比较简单的方法：深度优先搜索算法。
深度优先搜索算法是一种递归算法，可以从迷宫的起点开始，不断随机选择一个方向，往前走，直到无法再往前为止。
然后回到上一次的分支点，选择另一个方向继续走，直到整个迷宫路径都被探索完毕。
在探索的过程中，我们可以将经过的格子标记为0，表示可通过，同时记录路径上的所有分支点，方便后面生成迷宫时打通墙壁。
第四步，随机挖墙迷宫路径已经生成完毕，接下来我们需要随机挖墙，打通路径上的墙壁，让迷宫变成一张连接所有路径的图。
随机挖墙的方法也有很多种，这里介绍一种比较常见的方法：挖掉一些分支点周围的墙壁。
具体实现方法是选择一个随机的分支点，然后随机选择一个方向，检查该方向上的格子是否为墙壁，如果是墙壁，就把它打通，同时把该格子标记为已经访问过，以免重复挖掘。
然后继续在周围的格子中挑选下一个候选点，重复上述操作，直到所有的分支点周围的墙壁都被打通。
第五步，输出迷宫迷宫已经生成完毕，最后就是将其输出到屏幕上。
输出迷宫的方法也有很多种，这里介绍一种比较简单的方法：使用ASCII码字符表示迷宫。
具体实现方法是将生成的迷宫数组中的0标记为ASCII码字符' '（空格），将1标记为ASCII码字符'#'（井号），然后按照行列的顺序输出到屏幕上即可。
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语⾔实现⾛迷宫本⽂实例为⼤家分享了C语⾔实现⾛迷宫的具体代码，供⼤家参考，具体内容如下描述给⼀张个迷宫，问能否从起点⾛到终点，只能往上下左右⾛，不能斜着⾛输⼊多组测试数据，每组第⼀⾏两个正整数，分别为n和m表⽰n这个迷宫有n⾏m列(0<n,m<10)接着是n⾏m列，'#'表⽰路‘*'表⽰墙‘S'表⽰起点‘T'表⽰终点输出每组测试数据输出⼀个结果，如果能从S⾛到T，输出“YES”,否则输出“NO”输⼊样例：2 2S*#T3 3S*##T##输出样例：YESNO有两种⽅法可以解决这个问题第⼀种深度优先搜索：站在⼊⼝，考虑⾃⼰下⼀步可以⾛哪⾥，⾛到下⼀个位置后，再考虑下⼀步怎么⾛，⼀直⾛下去，直到没有路，然后再返回最近的⼀个岔路⼝，选其它任⼀条没试过的路，如果不能⾛，再尝试其他的路，直到这个岔路⼝的路全部试完，再回到上⼀个路⼝，看是否能⾛到出⼝，相当于⼀条路⾛到⿊#include<bits/stdc++.h>using namespace std;char a[20][20]; //存储迷宫字符数组int flag,m,n;int sdep_x[4]={-1,1,0,0},sdep_y[4]={0,0,-1,1};//控制上下左右⽅向int vis[20][20]; //标记⾛过的路void dfs(int x,int y){vis[x][y]=1; //代表被标记过了if(a[x][y]=='T') //找到出⼝{flag=1;return;}for(int i=0;i<4;i++) //搜索路径{int h=x+sdep_x[i];int l=y+sdep_y[i];if(a[h][l]!='*'&&!vis[h][l]&&h>=0&&h<n&&l>=0&&l<m)//搜索路径的条件{dfs(h,l);}}}int main(){while(cin>>n>>m){memset(vis,0,sizeof(vis));//初始化数组flag=0;int f,g;for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(a[i][j]=='S')//先找到路⼝{f=i;g=j;}}dfs(f,g);if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;}第⼆种⽅法⼴度优先搜索：这⼀步之后，把接下来⼀步的所有路都列出来，在之后的所有扩展之中，在以⼀个为下⼀步，再将所有的该步可以到达的下⼀步，全部列举出来，再将第⼆步的其他选择中的每⼀步，都⼀⼀做扩展，每次扩展，都要检查所扩展的地⽅有没有到达搜索的要求。
＃include〈stdio。
h〉＃include〈stdlib。
h>＃include〈time.h>#define stack_init_size 200#define stack_increment 10#define ERROE 0#define TRUE 1#define FALSE 0#define OVERFLOW 0＃define OK 1typedef int Status;typedef struct{int x;int y；}PosType;typedef struct {int ord; // 通道块在路径上的“序号”PosType seat; //通道块在迷宫中的“坐标位置”int di; //从此通道块走向下一通道块的“方向”}SElemType；typedef struct｛SElemType ＊base;SElemType ＊top；int stacksize；}SqStack;int mg［20］[20]；/*随机生成迷宫的函数/＊为了能够让尽量能通过,将能通过的块和不能通过的块数量比大致为2:1*/void Random()｛int i，j,k;srand(time（NULL)）；mg［1][0]=mg［1]［1]=mg[18］[19]=0; //将入口、出口设置为“0"即可通过for(j=0;j〈20;j++）mg[0][j］=mg［19］[j]=1；/*设置迷宫外围“不可走”,保证只有一个出口和入口＊/ for（i=2；i〈19；i++）mg[i］[0]=mg［i—1][19］=1; /＊设置迷宫外围“不可走”，保证只有一个出口和入口＊/ for(i=1;i〈19；i++）for（j=1；j<19；j++)｛k=rand（)％3; //随机生成0、1、2三个数if（k）mg[i]［j］=0；else｛if（（i==1&&j==1)|｜(i==18＆＆j==18)) /＊因为距入口或出口一步的路是必经之路，故设该通道块为“0”加大迷宫能通行的概率＊/mg[i][j］=0;elsemg[i］［j]=1；}｝｝//构造一个空栈Status InitStack(SqStack &s）{s。
简单的迷宫小游戏C语言程序源代码#include <stdio.h>#include <conio.h>#include <windows.h>#include <time.h>#define Height 31 //迷宫的高度，必须为奇数#define Width 25 //迷宫的宽度，必须为奇数#define Wall 1#define Road 0#define Start 2#define End 3#define Esc 5#define Up 1#define Down 2#define Left 3#define Right 4int map[Height+2][Width+2];void gotoxy(int x,int y) //移动坐标{COORD coord;coord.X=x;coord.Y=y;SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HA NDLE ), coord );}void hidden()//隐藏光标{HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);CONSOLE_CURSOR_INFO cci;GetConsoleCursorInfo(hOut,&cci); cci.bVisible=0;//赋1为显示，赋0为隐藏SetConsoleCursorInfo(hOut,&cci);}void create(int x,int y) //随机生成迷宫{int c[4][2]={0,1,1,0,0,-1,-1,0}; //四个方向int i,j,t;//将方向打乱for(i=0;i<4;i++){j=rand()%4;t=c[i][0];c[i][0]=c[j][0];c[j][0]=t;t=c[i][1];c[i][1]=c[j][1];c[j][1]=t;}map[x][y]=Road;for(i=0;i<4;i++)if(map[x+2*c[i][0]][y+2*c[i][1]]==Wall) {map[x+c[i][0]][y+c[i][1]]=Road; create(x+2*c[i][0],y+2*c[i][1]);}}int get_key() //接收按键{char c;while(c=getch()){if(c==27) return Esc; //Escif(c!=-32)continue;c=getch();if(c==72) return Up; //上if(c==80) return Down; //下if(c==75) return Left; //左if(c==77) return Right; //右}return 0;}void paint(int x,int y) //画迷宫{gotoxy(2*y-2,x-1);switch(map[x][y]){case Start:printf("入");break; //画入口case End:printf("出");break; //画出口case Wall:printf("※");break; //画墙case Road:printf(" ");break; //画路}}void game(){int x=2,y=1; //玩家当前位置，刚开始在入口处int c; //用来接收按键while(1){gotoxy(2*y-2,x-1);printf("☆"); //画出玩家当前位置if(map[x][y]==End) //判断是否到达出口{gotoxy(30,24);printf("到达终点，按任意键结束"); getch();break;}c=get_key();if(c==Esc){gotoxy(0,24);break;}switch(c){case Up: //向上走if(map[x-1][y]!=Wall){paint(x,y);x--;}break;case Down: //向下走if(map[x+1][y]!=Wall){paint(x,y);x++;}break;case Left: //向左走if(map[x][y-1]!=Wall){paint(x,y);y--;}break;case Right: //向右走if(map[x][y+1]!=Wall){paint(x,y);y++;}break;}}}int main(){int i,j;srand((unsigned)time(NULL)); //初始化随即种子hidden(); //隐藏光标for(i=0;i<=Height+1;i++)for(j=0;j<=Width+1;j++)if(i==0||i==Height+1||j==0||j==Width+1) //初始化迷宫map[i][j]=Road;else map[i][j]=Wall;create(2*(rand()%(Height/2)+1),2*(rand()%(Width/2)+1)); //从随机一个点开始生成迷宫，该点行列都为偶数for(i=0;i<=Height+1;i++) //边界处理{map[i][0]=Wall;map[i][Width+1]=Wall;}for(j=0;j<=Width+1;j++) //边界处理{map[0][j]=Wall;map[Height+1][j]=Wall;}map[2][1]=Start; //给定入口map[Height-1][Width]=End; //给定出口for(i=1;i<=Height;i++)for(j=1;j<=Width;j++) //画出迷宫paint(i,j);game(); //开始游戏getch();return 0;}。
基于C语⾔实现的迷宫算法⽰例本⽂实例讲述了基于C语⾔实现的迷宫算法。
分享给⼤家供⼤家参考，具体如下：利⽤c语⾔实现迷宫算法，环境是vc++6.0.#include<stdio.h>#include<time.h>#include<cstdlib>int visit(int,int);void setmaze();int maze[11][11]={{0,0,2,2,2,2,2,2,2,2},{2,0,2,2,0,2,0,2,0,2},{2,0,2,0,0,0,0,0,0,2},{2,0,2,2,2,0,2,0,0,2},{2,0,0,0,0,0,2,2,0,2},{2,2,0,2,2,0,2,2,0,2},{2,2,2,0,0,0,0,0,0,2},{2,0,2,0,2,0,2,2,0,2},{2,0,0,0,0,2,0,2,0,0},{2,2,2,2,2,2,2,2,2,2}};int startI,startJ; //定义⼊⼝变量int endI,endJ; //定义出⼝变量int success=0; //定义返回变量int p;void setStart() // 设置⼊⼝{printf("请设置迷宫⼊⼝（i,j）:");scanf("%d,%d",&startI,&startJ);}void setEnd() // 设置出⼝{printf("请设置迷宫出⼝（i,j）:");scanf("%d,%d",&endI,&endJ);}void setmaze() //设置迷宫图{int i,j,a,p;for(i=0;i<10;i++)for(j=0;j<10;j++){p=rand()%2;if(p==0) a=0;else a=2;maze[i][j]=a;}}void DisplayMaze() //打印迷宫{int i,j;for(i=0;i<10;i++){printf(" ");for(j=0;j<10;j++)if(maze[i][j]==2) printf("##"); //打印墙壁else printf(" "); //打印路径printf("/n");}}void Maze_PS() //输出迷宫路径{int i,j;if(visit(startI,startJ)==0) //寻找路径printf("/n没有找到出⼝！/n");else{maze[startI][startJ]=8;//设置⼊⼝标志maze[endI][endJ]=9;//设置出⼝标志printf("/n显⽰路径：/n");for(i=0;i<10;i++){for(j=0;j<10;j++){if(maze[i][j]==8) printf("☆");//标志⼊⼝else if(maze[i][j]==9) printf("○");//标志出⼝else if(maze[i][j]==2) printf("##"); //表⽰墙壁else if(maze[i][j]==1) printf(" >"); //表⽰路径else printf(" "); //通路}printf("/n");}}}int visit(int i,int j) //寻找迷宫路径函数，找到路径返回1，找不到路径返回0{maze[i][j]=1;if((i==endI)&&(j==endJ)) success=1; //找到出⼝，返回值success为1if((success!=1)&&(maze[i][j+1]==0)) visit(i,j+1); //检测右⾯通路，若通，向右移动 if((success!=1)&&(maze[i+1][j]==0)) visit(i+1,j); //检测下⾯通路，若通，向下移动 if((success!=1)&&(maze[i][j-1]==0)) visit(i,j-1); //检测左⾯通路，若通，向左移动 if((success!=1)&&(maze[i-1][j]==0)) visit(i-1,j); //检测上⾯通路，若通，向上移动 if(success!=1) maze[i][j]=0; //退回，⾃⾝标为0return success;}main(void) //主函数{int c1,c2;for(c2=1;c2==1;){srand(time(0));printf("显⽰迷宫：/n");for(c1=1;c1==1;){DisplayMaze();printf("按'1'输出新迷宫,'2'开始求解路径：/n");scanf("%d",&c1);rewind(stdin);//清除输⼊缓冲区if(c1==1) setmaze() ;}if(c1!=1&&c1!=2) {printf("Error!!/n");break;}setStart();setEnd();Maze_PS();printf("Continue?(1 to continue,2 to exit.1)");scanf("%d",&c2);if(c2==1) setmaze();else break;}system("pause");}希望本⽂所述对⼤家C语⾔程序设计有所帮助。
基于栈的C语言迷宫问题与实现一．问题描述多年以来，迷宫问题一直是令人感兴趣的题目。
实验心理学家训练老鼠在迷宫中寻找食物。
许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。
于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。
迷宫只有两个门，一个叫做入口，另一个叫做出口。
把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。
迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。
求解迷宫问题，即找出从入口到出口的路径。
一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1 表示不能通过。
现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n] 出去的路径。
下图是一个迷宫的示意图：迷宫示意图二．算法基本思想迷宫问题是栈应用的一个典型例子。
求解过程可采用回溯法。
回溯法是一种不断试探且及时纠正错误的搜索方法。
从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。
在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。
为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。
给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。
三．主要数据结构1.方阵栈：#define STACK_INI_SIZE 100typedef struct{int *top; //指向栈的顶端域int *base; //指向栈的低端域int length; //栈的长度int stacksize; //栈的最大长度}sqstack;2．产生迷宫的矩阵二维数组为了使每一个迷宫存在迷宫的边界和两个端口：入口、出口，设置了一个二维数组，在迷宫的周边定义为1，使得迷宫存在边界，并在（1,1），（x-2,y-2）初定义为0，即定义迷宫的出口，大大减小了无解的情况。
for(i=0;i<x;i++)for(j=0;j<y;j++)mg[i][j]=rand()%3;//产生随机数i=0;for(j=0;j<y;j++){mg[i][j]=1; //定义边界mg[j][i]=1;}i=y-1;for(j=0;j<x;j++) //定义边界mg[j][i]=1;i=x-1;for(j=0;j<y;j++)mg[i][j]=1;mg[1][1]=0; //定义出口和入口mg[x-2][y-2]=0;四．主要函数功能1．void initstack(sqstack *s);/*初始化栈*/将栈顶和栈底分别申请一段动态存储空间，将栈分配长度为100的空间，将栈的原始长度定义为22．void stackpush(sqstack *s,int);/*增加栈顶*/将栈的动态存储空间增加50，将栈顶指针上移相应高度，特殊情况单独考虑见程序。
3．void stackpop(sqstack *s);/*撤销栈顶*/栈空提示无法删除，其他情况删除栈顶。
4．void stackinput(sqstack *s);/*输出栈*/输出寻找到的一条迷宫路径5．int mgway(sqstack *s);/*迷宫路径*/寻找到可执行的一条迷宫路径6．void destorystack(sqstack *s);/*撤销栈S*/将栈内元素清空7．void makemg(sqstack *s);/*制造迷宫*/输入迷宫的长宽（2-15），并产生迷宫图五．算例（生成演算结果）本程序的运算环境为：codeblocks输入界面：输入错误则重新输入5*5的迷宫图及其路径：继续输入错误提示：重新输入结果：可以看到每个迷宫都存在“围墙”六．分析算法1.空间复杂度固定空间需求：25*25的二维迷宫数组可变空间需求：初始化栈中申请了100倍int型所占空间大小的动态空间，加入栈顶时额外申请50倍int型所占空间大小2.时间复杂度可以通过“程序步”对程序的时间复杂度进行测量，可以引入count计数器进行测量，考虑到其复杂程度，本程序将不采用此方法。
本程序的排错率较高，计算机会改掉没有通路的栈，并随机生成有通路迷宫，提高了程序的执行效率，并给迷宫添加了必要的围墙和出口、入口有助于执行效率的提高。
但对于路径的搜索，栈并没有引入方向指针，在后面，通过flag进行标记来确定栈的路径的寻找的，一定程度上会影响执行效率。
附录：C语言源程序#include<stdio.h>#include<stdlib.h>#define STACK_INI_SIZE 100#define STACKINCREMENT 50#define NULL 0typedef struct{int *top;int *base;int length;int stacksize;}sqstack;int mg[25][25];int m=1,n=1,x,y;/*********************************************/ main(){void initstack(sqstack *s);/*初始化栈*/void stackpush(sqstack *s,int);/*增加栈顶*/void stackpop(sqstack *s);/*撤销栈顶*/void stackinput(sqstack *s);/*输出栈*/int mgway(sqstack *s);/*迷宫路径*/void destorystack(sqstack *s);/*撤销栈S*/void makemg(sqstack *s);/*制造迷宫*/sqstack s;int i,flag1=1,flag2=1,flag3=1;char ch;srand((unsigned)time(NULL));while(flag1){initstack(&s);flag2=1;makemg(&s);i=mgway(&s);if(i==0)printf("此迷宫没有通路\n");elsestackinput(&s);destorystack(&s);printf("还继续么?");fflush(stdin);scanf("%c",&ch);while(flag2){if(ch=='n'||ch=='N'){flag1=0;flag2=0;}else if(ch=='y'||ch=='Y'){flag1=1;flag2=0;}else{printf("输入错误请重新输入");fflush(stdin);scanf("%c",&ch);}}}}/*********************************************/void initstack(sqstack *s)/*初始化栈*/{s->top=s->base=(int *)malloc(STACK_INI_SIZE*sizeof(int));if(!s->base)exit(1);s->stacksize=STACK_INI_SIZE;*(s->base)=0;s->top++;*(s->top)=101;s->top++;s->length=2;}/*********************************************/void stackpush(sqstack *s,int i)/*增加栈顶*/{if(s->length>=s->stacksize){printf("路过");s->base=(int *)realloc(s->base,(STACK_INI_SIZE+STACKINCREMENT)*sizeof(int));if(!s->base)exit(1);s->top=s->base+s->length;s->stacksize+=STACKINCREMENT;stackinput(s);}if(s->length==0){*(s->base)=i;s->top++;s->length++;}else{*(s->top)=i;s->top++;s->length++;}}/*********************************************/void stackpop(sqstack *s)/*删除栈顶*/{if(s->length==0)printf("栈空无法删除");if(s->length==1){s->top--;*(s->top)=*(s->base)=NULL;s->length=0;}else{s->top--;*(s->top)=NULL;s->length--;}}/*********************************************/void stackinput(sqstack *s)/*迷宫栈的输出*/{int w,x,y,z,i=0,*p;p=s->base;p++;printf("迷宫正确路径\n");while(p!=s->top){printf("(%d%d,%d%d)",x=*p/1000,y=*p/100%10,z=*p%100/10,w=*p%10);p++;i++;if(i==7){printf("\n");i=0;}}}/*********************************************/ int mgway(sqstack *s)/*迷宫路径*/{int gudge(sqstack *s,int);/*判断是否能通行*/int homing(sqstack *s);/*退栈后I所对应的方向*/ int i=1,j,k;while(s->top!=s->base){if(i<5)j=gudge(s,i);if(j==1&&i<5){k=m*100+n;stackpush(s,k);if(m==y-2&&n==x-2){return(1);}elsei=1;}else{if(m==0&&n==0)return(0);else if(i==4||i==5){i=homing(s);stackpop(s);i++;}elsei++;}}return(0);}/*********************************************/ int gudge(sqstack *s,int i)/*退栈后i所对应的方向*/ {int echo(sqstack *s);if(i==1)n++;if(i==2)m++;if(i==3)n--;if(i==4)m--;if((mg[m][n]==0||mg[m][n]==2)&&echo(s))return(1);else{if(i==1)n--;if(i==2)m--;if(i==3)n++;if(i==4)m++;return(0);}}/*********************************************/ int echo(sqstack *s){int i,*p,*q;i=m*100+n;p=s->top;q=s->base;q++;p--;while(p!=q&&*p!=i)p--;if(*p==i)return(0);else}/*********************************************/int homing(sqstack *s)/*i退位后所对应的方向*/{int a,b,c,d,*q;q=s->top;q--;a=(*q)/100;b=(*q)%100;q--;c=(*q)/100;d=(*q)%100;m=(*q)/100;n=(*q)%100;if(a==c){if(d-b==1)return(3);else if(d-b==-1)return(1);}else if(b==d){if(c-a==1)return(4);else if(c-a==-1)return(2);}return(0);}void destorystack(sqstack *s){if(*(s->base)!=NULL)free(s->base);s->length=0;}/*********************************************/ void makemg(sqstack *s)/*创建迷宫及输出迷宫图的函数*/ {int mgway(sqstack *s);void clearstack(sqstack *s);int flag=1,flag2=1,i,j,k;char ch;{printf("请输入迷宫的长宽(长度范围2-15,宽范围2-15)\n");printf("输入长");fflush(stdin);scanf("%d",&y);printf("输入宽");fflush(stdin);scanf("%d",&x);if(x<16&&x>3&&y>3&&y<16)flag=0;if(flag==0)printf("自动筛选能通过的迷宫需要一段时间,请耐心等待,如20秒后无法显示出迷宫样本请重试... ...\n");}flag=1;while(flag2){m=1;n=1;for(i=0;i<x;i++)for(j=0;j<y;j++)mg[i][j]=rand()%3;i=0;for(j=0;j<y;j++){mg[i][j]=1;mg[j][i]=1;}i=y-1;for(j=0;j<x;j++)mg[j][i]=1;i=x-1;for(j=0;j<y;j++)mg[i][j]=1;mg[1][1]=0;mg[x-2][y-2]=0;k=mgway(s);if(k==1)flag2=0;elseclearstack(s);}printf(" ");for(i=0;i<y;i++)printf("%2d",i);printf("\n ");for(i=0;i<y;i++)printf("↓");printf("\n");for(i=0;i<x;i++){printf("%2d→",i);for(j=0;j<y;j++){if(mg[i][j]==2)printf("0 ");elseprintf("%d ",mg[i][j]);}printf("\n");}}/*********************************************/ void clearstack(sqstack *s)/*清空栈对于此程序而言*/ {s->top=s->base;*(s->base)=0;s->top++;*(s->top)=101;s->top++;s->length=2;}。
