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

C语⾔递归实现迷宫寻路问题迷宫问题采⽤递归和⾮递归两种⽅法，暂时完成递归⽅法，后续会补上⾮递归⽅法#include<stdio.h>#include<stdbool.h>bool findPath(int a[][8],int i,int j){//递归找出⼝if(i==6&&j==6)//如果找到了⽬标a[6][6]则返回truereturn true;if(a[i][j]==0)//若当前路径未被找到，则继续{a[i][j]=2;//当前⾛的路径置为2，表⽰⾛过if(findPath(a,i+1,j)||findPath(a,i,j+1)||findPath(a,i-1, j)||findPath(a,i-1,j))//每个⽅向都判断，依次展开递归，寻找最佳路径return true;//若选择的路径可以⾛，则返回trueelse{//若当前选择的路径不能⾛a[i][j]=0;//弹栈并恢复路径，回退到上⼀次的位置return false;}}else//未能找到最终点return false;}void print(int a[][8])//打印当前的⼆维数组表{for(int i=0;i<8;i++){for(int j=0;j<8;j++){printf("%d ",a[i][j]);}printf("\n");}}int main(){int a[8][8]={0};for(int i=0;i<8;i++)//设置围墙和障碍物{a[0][i]=1;a[i][0]=1;a[7][i]=1;a[i][7]=1;}a[3][1]=1;a[3][2]=1;print(a);printf("-----------after find path-----------\n");findPath(a, 1, 1);print(a);}。

C语⾔实验：迷宫问题（搜索，C语⾔实现栈、队列）Description给定迷宫起点和终点，寻找⼀条从起点到终点的路径。

(0,1)(2,0)起点(1,1)(1,2)(1,3)(1,4)(2,0)(2,1)(2,4)(3,0)(3,1)(3,2)终点（3,4）(4,1)上图中黄⾊代表墙，⽩⾊代表通路，起点为(1,1)，终点为(3,4)。

要求搜寻策略是从起点开始按照“上、下、左、右”四个⽅向寻找终点，到下⼀个点继续按照“上、下、左、右”四个⽅⾯寻找，当该结点四个⽅向都搜寻完，但还没到终点时，退回到上⼀个点，直到找到终点或者没有路径。

⽐如上图从(1,1)开始，向上(0,1)不通，向下到(2,1)；到了(2,1)后继续按“上、下、左、右”四个⽅⾯寻找，上已经⾛过，向下到(3,1)；到(3,1)后上已经⾛过，下和左不通，向右到(3,2)；到(3,2)四个⽅⾯都不通，回到(3,1)四个⽅向都不通，再回到(2,1),(1,1)；到达(1,1)后下已经⾛过，左不通，继续向右⾛，重复这个过程最后到达(3,4)。

Input第⼀⾏两个数m和n表⽰迷宫的⾏数和列数。

迷宫⼤⼩不超过100×100第⼆⾏四个数x1,y1,x2,y2分别表⽰起点和终点的坐标。

接下来是m⾏n列的数，⽤来表⽰迷宫，1表⽰墙，0表⽰通路。

Output从起点到终点所经过的路径的坐标。

如果不存在这样的路径则输出“No Path!”。

Sample Input5 61 1 3 41 1 1 1 1 11 0 0 0 0 11 0 1 1 0 11 0 0 1 0 11 1 1 1 1 1Sample Output(1 1)(1 2)(1 3)(1 4)(2 4)(3 4)1.思路：（1）若当前点是终点，dfs函数返回1；（2）若不是终点，将此点标记为1，对该点4个⽅向进⾏搜索，实现⽅式为定义int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 通过⼀个⼩循环： for(int i = 0; i < 4; i++) {　 position nextp; nextp.x = dir[i][0] + now.x;nextp.y = dir[i][1] + now.y;...... }　进⾏搜索；若该点的下⼀个点nextp不是墙，未⾛，并且没有超界则将nextp压⼊栈中，递归调⽤dfs，若此过程经过（1）判断返回了1，说明最终找到了通往终点的路，便可以返回1，结束函数，此时栈中已储存了通往终点的路径，若没有通路，则弹出栈顶元素，根据递归原理该路径上的所有点都会弹出并标记未⾛，回溯到之前的点，继续向其他⽅向搜索，直到找到终点或遍历完整个图。

基于栈的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,即定义迷宫的出口,大大减小了无解的情况。

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请按任意键继续. . .*/。