数据结构课程设计-迷宫问题

数据结构课程设计-迷宫问题迷宫求解问题题目描述用一个m×n的矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对给定的迷宫，求出找到的第一条从入口到出口的通路，或得到没有通路的结论。我们指定:迷宫的入口为矩阵的左上角（1,1），迷宫的出口为右下角（m,n）;路径的探索顺序依次为"东南西北"（即：右下左上）。输入第一行输入两个整数，空格间隔，分别表示矩阵的行数m和列数n；接下来的连续m行，输入迷宫矩阵的信息。输出求得的通路以三元组(i,j,d)的形式输出。其中：i,j指示迷宫的一个坐标;d表示走到下一坐标的方向(数字1表示东，数字2表示南，数字3表示西，数字4表示北);终点d值为0。样例输入98001000100010001000001101011100100001000001000101011110011100010111000000样例输出(1,1,1)(1,2,2)(2,2,2)(3,2,3)(3,1,2)(4,1,2)(5,1,1)(5,2,1)(5,3,2)(6,3,1)(6,4,1)(6,5,4)(5,5,1)(5,6,1)(5,7,2)(6,7,2)(7,7,2)(8,7,2)(9,7,1)(9,8,0)。ok，具体的题目就如上了大概意思呢，我们输入一个全是0或1的二维数组，要输出一堆三元组，从左上角开始走，到右下角为出口，三元组：前两个数字为坐标，最后的数字为移动的方向，这里东南西北分别对应1234本题的本意是考验对栈的操作，以及对递归的运用，我们上代码，后分析。#include<stdio.h>#include<stdlib.h>#defineerror(str)fprintf(stderr,"%s",str),exit(1)typedefstructnode{inti,j,k;structnode*next;}stack;stack*s;//这里直接声明stack*sstack*creat({stack*s=(stack*)malloc(sizeof(stack));s->i=0,s->j=0,s->k=0,s->next=NULL;returns;}intisempty(stack*s){returns->next==NULL;}voidpush(stack*s,inti,intj,intk){stack*front=(stack*)malloc(sizeof(stack));front->i=i,front->j=j,front->k=k;front->next=s->next;s->next=front;}voidpop(stack*s){if(isempty(s))error("isalreadyempty");stack*front=s->next;s->next=s->next->next;free(front);}intfindway(inta[][100],intei,intej,intsi,intsj,inti,intj)//这里采用递归算法寻路{inte=0;//用e做flaga[i][j]=2;//这里主要是用于替换对任何数字都可以if(i==ei&&j==ej)e=1;if(e!=1&&j+1<=ej&&a[i][j+1]==0)//往东{push(s,i,j,1);if(findway(a,ei,ej,si,sj,i,j+1)==1)//这里通过递归继续整个算法return1;}if(e!=1&&i+1<=ei&&a[i+1][j]==0)//往南{push(s,i,j,2);if(findway(a,ei,ej,si,sj,i+1,j)==1)return1;}if(e!=1&&j-1>=sj&&a[i][j-1]==0)//往西{push(s,i,j,3);if(findway(a,ei,ej,si,sj,i,j-1)==1)return1;}if(e!=1&&i-1>=si&&a[i-1][j]==0)//往北{push(s,i,j,4);if(findway(a,ei,ej,si,sj,i-1,j)==1)return1;}if(e!=1){a[i][j]==0;pop(s);}returne;}voidshow(stack*s){if(s->next)show(s->next);if(s->i)printf("(%d,%d,%d)",s->i,s->j,s->k);}intmain({s=creat(;//stack*s以在前面声明过inti,j,l,k;scanf("%d%d",&i,&j);inta[100][100];for(l=1;l<=i;l++)for(k=1;k<=j;k++)scanf("%1d",&a[l][k]);if(findway(a,i,j,1,1,1,1)==1){push(s,i,j,0);//这里是最后的情况，输出位置和0.show(s);}return0;}。首先我们需要对栈的操作函数，这里我们要用到创建，入栈，出栈，判空，这些函数都很容易写，便不细讲。博主的思路是通过暴力遍历每一条的方式去找到出路，因此是一个全程的递归过程，并且我对算法加了返回值，是为了最后的if判断，好，接下来我们细看算法思路我刚开始想着是直接对数组进行蛮横的右下探索，但是这条路实质上并没有用到栈的性质，后来结合一些朋友的帮助想到了不断的递归的过程。这里的函数我也很形象的命名为findway，那么首先，我们给整个二维数组设置一个外环的全为1的套，这样就等于堵死了在外的所有路，然鹅实际上，看代码不难发现我们并没有真的设置套，而是设置了范围，同时我们的数值都是从索引1开始取的，这样就够了这样一个结构如图：（a代指各个数字）而我们核心算法就是同归递归遍历所有的路，我们从第一条路举例开始分析，（以题中所给数字）我们进入算法，首先，从0开始，判断进入下一层函数，这时候是往东，因此到了坐标（1,2），入栈，接着往南，进入坐标（2,2），入栈，又往南进入（3,2），接着两次往东到（3,4）不断的入栈，那么这时候有朋友就要问了，从判断角度来说，往西在往北的前面这意味着他又回到之前的位置了，进而又往东往复循环。朋友，不会的，注意看算法前有一句a[i][j]=2;//这里主要是用于替换对任何数字都可以，这个数字会覆盖你走过的每步，也就是说你走过之后他就不再是0了而是2，所以他不符合回去的条件，只能选择往北走，到（2,4）接着，往东两次，往北一次，往西三次到了（1,4）此时的矩阵是这样的。我们在红点这。这时候没有路了，那么我们的e就不等于1了于是出栈，接着每一层递归都从if判断条件跳出，一个一个出栈一直出到刚开始递归入口，从下一个if进去继续判断，总体就是这样的过程，如果对递归运用不太熟练可能理解有点苦难，不过多看几遍就好，应该没什么问题，这里博主已经将语言化为最简模式讲出来了，这样一直遍历，只到最后到了范围，这是e等于1直接return，又一路return出来如果是到最后了，那么我们递归入口的返回值也是1，这时候我们对入栈的数递归输出就好。这里递归输出是因为栈的性质是一步一步往里存的，而我们的出栈操作只能看到顶也就是最后存入的，所以我们递归让他从刚开始存入的开始输