求解迷宫问题(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");}。

求迷宫问题就是求出从入口到出口的路径。

在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。

为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。

首先用如图3.3所示的方块图表示迷宫。

对于图中的每个方块,用空白表示通道,用阴影表示墙。

所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下:int mg[M+1][N+1]={ /*M=10,N=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{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} }; 伪代码：c语言描述如下：6/ 2void mgpath() /*路径为:(1,1)->(M-2,N-2)*/{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-2 && j==N-2) /*找到了出口,输出路径*/ {瀠楲瑮?迷宫路径如下:\n);for (k=0;k<=top;k++){printf(\ (%d,%d),Stack[k].i,Stack[k].j); if ((k+1)%5==0) printf(\);}6/ 3printf(\);return;}find=0;while (di<4 && 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;}6/ 4if (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;/*让该位置变为其他路径可走方块*/top--;}}牰湩晴尨没有可走路径!\n);}6/ 5（范文素材和资料部分来自网络，供参考。

求迷宫问题就是求出从入口到出口的路径。

在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。

为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。

首先用如图所示的方块图表示迷宫。

对于图中的每个方块,用空白表示通道,用阴影表示墙。

所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下:int mg[M+1][N+1]={ /*M=10,N=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} }; 伪代码：c语言描述如下：void mgpath() /*路径为:(1,1)->(M-2,N-2)*/ {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-2 && j==N-2) /*找到了出口,输出路径*/{printf("迷宫路径如下:\n");for (k=0;k<=top;k++){printf("\t(%d,%d)",Stack[k].i,Stack[ k].j);if ((k+1)%5==0) printf("\n");}printf("\n");return;}find=0;while (di<4 && 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;/*让该位置变为其他路径可走方块*/top--;}}printf("没有可走路径!\n");}。

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"` 和 `"*"`,其他地方都为空。

数据结构实验报告——迷宫求解1、问题描述以一个m x n的长方矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。

设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的结论。

2、需求分析1、以二维数组migong[M][N]表示迷宫，其中migong[0][j]和migong[i][0](0<=j,i<=N)为添加的一圈障碍。

数组中以元素0表示通路，1表示障碍，迷宫的大小理论上可以不限制。

2、迷宫数据由程序提供，用户只需要进行选择迷宫就行。

迷宫的入口和出口由程序提供。

3、若设定的迷宫存在通路，则以长方形矩阵的形式将迷宫及其通路输出到标准终端上，其中“0”表示障碍，“2”表示通过的路径，“3”表示死胡同，没有显示的区域表示没有到达过的地方。

4、本程序只求出一条成功的通路。

但是只要对函数进行小量的修改，就可以求出其他全部的路径。

5、程序执行命令为：（1）、创建迷宫；（2）、求解迷宫；（3）、输出迷宫。

3、概要设计a、设定栈的抽象数据类型定义：ADT zhan{数据对象：D={ai|ai属于yanshu，i=1、2…n，n>0}数据关系：R={<ai-1,ai>|ai-1,ai属于D，i=2,3,…n}基本操作：gouzhan(*s,*migong)操作结果：构造一个空栈push（*s，*e）初始条件：栈已经存在操作结果：将e所指向的数据加入到栈s中pop（*s,*e）初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素getpop（*s，*e）初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素popover(*s)初始条件：栈已经存在操作结果：输出栈中的所有元素，同时清空栈stackempty(*s)初始条件：栈已经存在操作结果：判断栈是否为空。

若栈为空，返回1，否则返回0destroy(*s)初始条件：栈已经存在操作结果：销毁栈s}ADT zhanb、设定迷宫的抽象数据类型定义ADT yanshu{数据对象：D={ai,j|ai,j属于{‘’、‘0’、‘2’、‘3’},0<=i<=M,0<=j<=N}数据关系：R={ROW,COL}ROW={<ai-1,j,ai,j>|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N}COL={<ai,j-1,ai,j>|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N}基本操作：gouzhaomigong(*migong,m,n)初始条件：二维数组migong[m][n]已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。

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语言版递归求解迷宫问题用递归函数求解迷宫问题(求出所有解)编译环境：Dev-C++ 4.9.9.2日期：2011年2月12日*/#include&lt;stdio.h&gt;// 迷宫坐标位置类型struct PosType{int x; // 行值int y; // 列值};#define MAXLENGTH 25 // 设迷宫的最大行列为25typedef int MazeType[MAXLENGTH][MAXLENGTH]; // [行][列]// 全局变量struct PosType end; // 迷宫终点位置MazeType m; // 迷宫数组int x, y; // 迷宫行数，列数// 定义墙元素值为0,可通过路径为-1,通过路径为足迹// 输出解void Print(int x,int y){int i,j;for(i=0;i&lt;x;i++){for(j=0;j&lt;y;j++)printf(&quot;%3d&quot;,m[i][j]);printf(&quot;\n&quot;);}printf(&quot;\n&quot;);}// 由当前位置cur、当前步骤curstep试探下一点void Try(struct PosType cur,int curstep){int i;struct PosType next; // 下一个位置// {行增量,列增量}struct PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};// 移动方向,依次为东南西北for(i=0;i&lt;=3;i++) // 依次试探东南西北四个方向{next.x=cur.x+direc[i].x;next.y=cur.y+direc[i].y;if(m[next.x][next.y] == -1) // 是通路{m[next.x][next.y]=++curstep;if(next.x != end.x || next.y != end.y) // 没到终点Try(next,curstep); // 试探下一点(递归调用)elsePrint(x,y); // 输出结果m[next.x][next.y]=-1; // 恢复为通路，试探下一条路curstep--;}}}// 0为墙，-1为通道int main(){struct PosType begin; //起点int i,j,x1,y1;printf(&quot;请输入迷宫的行数,列数(包括外墙)：（空格隔开）&quot;); scanf(&quot;%d%d&quot;,&amp;x,&amp;y);for(i=0;i&lt;x;i++) // 定义周边值为0(同墙){m[0][i]=0; // 迷宫上面行的周边即上边墙m[x-1][i]=0;// 迷宫下面行的周边即下边墙}for(j=1;j&lt;y-1;j++){m[j][0]=0; // 迷宫左边列的周边即左边墙m[j][y-1]=0;// 迷宫右边列的周边即右边墙}for(i=1;i&lt;x-1;i++)for(j=1;j&lt;y-1;j++)m[i][j]=-1; // 定义通道初值为-1printf(&quot;请输入迷宫内墙单元数(即墙的个数)：&quot;);scanf(&quot;%d&quot;,&amp;j);if(j)printf(&quot;请依次输入迷宫内墙每个单元的行数,列数：（空格隔开）\n&quot;); for(i=1;i&lt;=j;i++){scanf(&quot;%d%d&quot;,&amp;x1,&amp;y1);m[x1][y1]=0;}printf(&quot;迷宫结构如下:\n&quot;);Print(x,y);printf(&quot;请输入起点的行数,列数：（空格隔开）&quot;);scanf(&quot;%d%d&quot;,&amp;begin.x,&amp;begin.y);printf(&quot;请输入终点的行数,列数：（空格隔开）&quot;);scanf(&quot;%d%d&quot;,&amp;end.x,&amp;end.y);m[begin.x][begin.y]=1;Try(begin,1); // 由第一步起点试探起system(&quot;pause&quot;);return 0;}/*输出效果：请输入迷宫的行数,列数(包括外墙)：（空格隔开）4 4请输入迷宫内墙单元数(即墙的个数)：1请依次输入迷宫内墙每个单元的行数,列数：（空格隔开）1 2迷宫结构如下:0 00 00 -1 0 00 -1 -1 00 0 0 0请输入起点的行数,列数：（空格隔开）1 1 请输入终点的行数,列数：（空格隔开）2 2 0 0 0 00 1 0 00 2 3 00 0 0 0请按任意键继续. . .*/。