前言

今天是美好的一天，现在是体育课时间，我神奇的体育老师让我们男生需要做40个俯卧撑作为期末作业，可惜啊可惜，我差了一丝丝，这个东西对于我这种高瘦子还是有很大的挑战的，我现在能充分的感觉到码字的手已经不是那么的正常了，本人是热爱运动的，但是对于引体向上和俯卧撑这种运动我从事感到无可奈何，难！难！难！所以各位同学一定要加强锻炼哦！今天的这篇博客是比较特殊的一次，因为现在是北京时间：2022/12/30/17:06 ，可以看出现在不是凌晨，本来确实是想在凌晨的时候将这篇博客给产出的，但是怕因为困而影响了质量，所以我留到了现在来写。ok！我们现在就开始学习一下有关数据结构中的迷宫问题，我们从初阶的迷宫问题到进阶迷宫问题。

1.初阶迷宫题目

题目描述：定义一个二维数组N*M(其中2<=N<=10,2<=M<=10)，如下图所示：

 int maze[5][5] = { 0 1 0 0 0
                    0 1 1 1 0
                    0 0 0 0 0 
                    0 1 1 1 0
                    0 0 0 1 0
                   }

并且此时的这个二维数组表示的就是一个迷宫，其中1表示的是墙壁，0表示的是可以走的路，只能横着或者竖着走，不可以斜着走，要求编程找出从左上角到右下角的最短路线，入口点为[0,0],即第一格是可以走的路

输入描述：输入两个整数，分别表示二维数组的行数，列数。在输入相应的数组 ，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解，不考虑多解的情况，即迷宫只有一条通道

输出描述：左上角到右下角的最短路径，格式如样列所示

输入：5  5  

       0  1  2  3  4       外围属于下标标识

0     0  1  0  0  0

1     0  1  1  1  0

2     0  0  0  0  0

3     0  1  1  1  0

4     0  0  0  1  0

输出

(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)

来到这个位置我相信很多的同学对题目的意思看的还不是很清楚，只是对输入和输出的描述有了一些的想法，但是这个位置我想建议同学们，我们一定在看到一个题目的时候不要先去看输入和输出的描述，一定要把题意给审清，否则我们很有可能就是因为没有把题目好好看，重点去关注输出和输入用例而导致我们做不出这个题目，当然那种大神级别的同学当然是有自己的做题方法的，那是因为人家已经是身经百战了，当时如果有刚开始做题目的同学，我们一定要把题意一个一个字的去研读清楚，然后再结合输入和输出用例来自我尝试解决这个问题，否则你就会发现很多题目不是做不了而是题意没有看清导致，所以这样就有一些适得其反了。所以接下来我们就来一起重新再研读一下这个题目。

1.  二维数组表示迷宫

2.  1表示步可以走，0表示可以走

3.  只能上下左右的走

4.  入口在左上角，出口在右下角

5.  只有唯一的一条通路（区别于下面的迷宫进阶问题）

6.（0，0）表示的就是入口

所以当我们弄清楚了这6点并且此时结合这输入和输出的用例，我们就可以开始思考如何实现这些要求了，切记，我们应该一个一个问题的想着如何可以更好的实现，不要把6个问题融合成一个问题来考虑如何实现，这个就是一个分割子问题的方法来解题，能减小我们的做题压力，并且发现自己的缺漏。

例如：第一步，我要实现用二维数组构造一个迷宫出来，所以我此时就应该先解决这个问题

想如何用二维数组构造迷宫呢？

假如此时你对二维数组这一块的知识掌握的还不是很好，或者是很久没有涉及过二维数组，有一些忘记了，此时我们就可以先去巩固或者复习一下二维数组的知识，然而搞明白了之后，我们再来解决眼前的这个问题。

当然这只是一个例子，我知道很多同学对二维数组玩的都是很好的，不像我。

但是我们碰到的所有问题都是这样，当我对这个小问题不理解的时候，我就应该要先去把整个小问题给解决，然后再来解决进一步的问题，一个一个小问题，最后解决大问题，然后一个一个大问题，最后成为算法大佬。

所以以上就是我个人对做题的一些浅薄见解

在此留作纪念，希望自己是一直这样做下去的，希望自己在以后的某一天，也有玩转算法的时候。并且此时希望看到这里的同学或者算法大佬能够分享一下自己的做题方法和指正我的做题方法。

所以这里我们正式开始对上面的问题进行解答

首先，我们想要找通路，就需要走起来，如何走起来呢？

此时就是判断我的maze[0][0]的上下左右是否有通路，有的话，我就走，这样我就可以从maze[0][0]的位置走到我的第二个位置了，但是此时当我来到第二个位置的时候，我还需要继续的走，我该从那个方向走呢？是上还是下，还是左，还是右呢？所以此时思路来到这里，我们就应该意识到有两个问题要解决 了。

第一个问题：怎么走？

第二个问题：怎么一直走？

想明白这两个问题我们就可以很好的找到这条唯一的通路了

第一个问题

此时我们可以意识到想要走，我就要考虑应该往那个方向走，但是此时又要想到在迷宫中只有位置是0的位置才可以走，位置是1的并不可以走，并且我只能走上下左右不可以走斜线，想到了这几个点此时我们就应该要知道，我们应该要对maze[0][0]的上下左右进行判断，判断那个方向是0那个方向不是0，这样才可以在上下左右其中有0的时候，我就让它往数字0的位置走，并且当四个方向都没有0的时候，我们直接就可以返回这个迷宫没有通路。

bool IsPass(int** maze, int n, int m, position pos)
{
  if (pos.row >= 0 && pos.row < n && pos.col >= 0 && pos.col < m && maze[pos.row][pos.col] == 0)
  {
    return true;
    }
  else
  {
    return false;
  }
}

此时可以看出这个if语句中的条件就是判断我的下一个位置是可以走还是不可以走的

我们进行分步理解：

pos.row >= 0 && pos.row < n && pos.col >= 0 && pos.col < m

while (scanf("%d%d", &n, &m) != EOF)

此时的这两句代码中 row表示行 col表示列  n表示此时我们输入的n行，m表示我们输入的m列，此时就可以明显可以看出，我maze[0][0]想要走动起来，它的到达的下一个位置首先必须要满足这两个条件，也就是把maze[0][0]可以走的位置控制在我的二维数组之中，例：maze[0][0]此时肯定是不可以往上走的，所以就算此时maze[0][0]是0，它也不可以走，因为不在迷宫的范围之内。

并且此时代码中的  maze[pos.row][pos.col] == 0 就不用我说了吧！就是判断我的下一个位置是否为0，因为为0我才可以走，当然上面有提到，是在满足范围的前提之下。当然有的同学会不理解为什么是maze中的下标是[pos.row]和[pos.col]，那是因为此时我们可以把坐标给分装成一个结构体，利用结构体来表示我的坐标，如下所示：

typedef struct Position
{
  int row;
  int col;
}position

但是思路来到这里，有的同学会问，不是要进行四个方向的判断吗？怎么没看见四个方向呢？这里是因为我们把四个方向的控制放在了如何一直进行四个方向的判断中了，也就是如何实现一直走的问题中了，当然这边我们先透露一下，主要就是涉及函数的递归。

第二个问题

此时我们解决了不管是maze[0][0]还是下一个位置的上下左右的判断，使我们可以找到前往下一个位置的通路了，但是此时当我再一次进行上下左右的判断是首先会有一个问题？只有解决这个问题我们才可以更好的进行第二个问题。

就是刚刚我的位置也就是上一个位置肯定是数字为0的位置，此时我再进行上下左右的判断的时候肯定是就会导致我走回头路的，所以我们要解决上一个位置为0的问题。

解决方法：就是每次当我要进行上下左右的判断通路的时候，先将上一个位置给置换成非0

此时我们就可以很好的进入到第二个问题了，也就是如何实现一直走的问题，也就是如何进行一直判断的问题，当然也就是这个迷宫题目中最核心的一步。当然这个问题的解决方法也可以帮我们解决当一个位置处有两个或两个以上的通路的时候，如何把每一条通路都给走一遍，然后找到那条真正可以到出口的通路   和  解决我如何从一条死路之中给返回到通路之中的问题。并且此时这个问题的解决方法就会涉及到了有关二叉树的深度优先遍历的问题，当我们在学习二叉树的时候，我们可以知道不管是我们遍历二叉树，还是算二叉树的叶子结点等问题都会涉及到递归二叉树的左子树和右子树的过程，所以此时我们就可以把迷宫中的四个方向的判断给想象成二叉树，相当于我的二叉树是判断两个方向而我的迷宫是判断四个方向，原理都是相同的，所以此时我们对四个方向的判断和找到死路后返回到通路和如何找到真正的通路都是使用我们二叉树中学的深度优先遍历来解决的，总之就是我们在二叉树中熟知的递归问题，在这个问题中我们也还是使用递归来解决，并且这里使用递归解决是非常合理有效的，一下就能解决弄的我们头痛的问题。

并且这边我们对二叉树的深度优先遍历做一个小小的回顾：

二叉树深度优先遍历：例：           0

                                                 0     0

                                             0   0   0    0

                                          0  

                                       0  最深的位置

表示的意思就是我先往深了走，就是一直往下走，直到走到最深的地方，此时走到最深的那个0的位置，此时不可以往下走了之后，我就返回，返回到上面的那个0，然后发现此时的这个0只有左子树没有右子树，所以再返回，同理没有右子树再返回，直到有右子树，此时就可以继续往我的右子树的方向走（也就是此时的右子树类似于我的迷宫的第二个通路，此时向第二个通路走），所以我的迷宫问题就非常像是我的二叉树的深度优先问题，所以此时通过这个深度优先的思想，我就可以解决多通路的问题了，并且这边如果不理解的话就可以想想自己当初画的或者是老师画的递归的展开图来结合着思考一下。

所以递归展开图是非常的重要的

我们结合代码来更好的分析一下：（代码中注释给全了，方便我们更好的理解代码）

bool GetMazePath(int** maze, int n, int m, position cur)
{
  StackPush(&path, cur);//此时就是将我的cur给入栈，但是要注意回溯的位置的坐标是不需要入栈的，所以要处理一下
  //但是此时我的递归是要有停止条件的（当然此时的停止条件也就是我找到了迷宫的出口就表示我递归的停止条件）
  if (cur.row == n - 1 && cur.col == m - 1)
  {
    return true;
  }
  //寻找通路
  //有了起始位置cur，此时我就开始探测我的cur位置的上下左右四个方向
  position next;
  maze[cur.row][cur.col] = 2;//就是直接把此时我在的这个位置给置成非0就行，这样就可以防止走回头路了
  //上
  next = cur;
  next.row -= 1;//表示next的上就是此时next的行的下标减1
  if (IsPass(maze, n, m, next))//此时这个就是判断此时的这个位置是否可以通
  {
    //GetMazePath(maze, n, m, next);//此时这个就是递归，把此时找到的通路next又重新给给我的cur，这样就可以完美的实现往下寻找通路
    //并且此时当我如果在上下左右中的其中之一已经找到了的话，我就可以不需要再找了，所以此时的这个函数需要判断一下，然后给一个返回值
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
  //下
  next = cur;
  next.row += 1;
  if (IsPass(maze, n, m, next))//此时这个就是判断此时的这个位置是否可以通
  {
    //GetMazePath(maze, n, m, next);//此时这个就是递归，把此时找到的通路next又重新给给我的cur，这样就可以完美的实现往下寻找通路
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
  //左
  next = cur;
  next.col -= 1;
  if (IsPass(maze, n, m, next))//此时这个就是判断此时的这个位置是否可以通
  {
    //GetMazePath(maze, n, m, next);//此时这个就是递归，把此时找到的通路next又重新给给我的cur，这样就可以完美的实现往下寻找通路
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
  //右
  next = cur;
  next.col += 1;
  if (IsPass(maze, n, m, next))//此时这个就是判断此时的这个位置是否可以通
  {
    //GetMazePath(maze, n, m, next);//此时这个就是递归，把此时找到的通路next又重新给给我的cur，这样就可以完美的实现往下寻找通路
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
  StackPopt(&path);//这个位置来一个出栈，就可以很好的解决我的回溯问题，因为return false 就是说明这个坐标的位置处不是我的通路，所以在return false之前出栈，就是我最好的时机 
  return false;//表示只要上述有任何一个位置可以通就会return true; 上述四个位置都不可以通此时代码就来到这个位置就return false;

我们此时先不管入栈和出栈的问题，待会再细细的把入栈出栈的问题分析清楚，我们先分析有关迷宫的走法上的，先不管迷宫通路的打印问题。

例：此时的这句代码就是我的出口所在的位置，因为由题意可以知道出口是在右下角的，所以只需要把row和col的坐标控制在（n-1，m-1）处就可以找到出口了，并且可以明显看出此时的这个if语句中的条件和这个if语句就是我的递归条件，递归停止的条件。

  if (cur.row == n - 1 && cur.col == m - 1)
  {
    return true;
  }

例：此时的next就是我们上述所说的结构体中的row和col的位置，也就是坐标位置，并且maze[cur.row][cur.col] = 2; 这句代码就是为了在我走到了通路，来到了下一个位置，要进行下一次的上下左右进行判断的时候，先把我的上一个位置给置换成非0，然后这样才可以防止走回头路

  position next;
  maze[cur.row][cur.col] = 2;//就是直接把此时我在的这个位置给置成非0就行，这样就可以防止走回头路了

例： next = cur;这句代码表示的就是把cur的坐标给给我的next，例如当我现在是在maze[0][0]的位置，也就是把入口的位置先从下面的主函数（main）中传值上来，然后对其进行相应坐标的加减，这样我就可以很好的表示出maze[0][0]的上下左右的位置了，所以此时的的maze[-1][0] 、maze[1][0] 、maze[0][-1] 、maze[0][1] ，就是表示maze[0][0] 的上下左右的位置的坐标，如下代码中：

    //上
    next = cur;
    next.row -= 1;
    //下
    next = cur;
    next.row += 1;
    //左
    next = cur;
    next.col -= 1;
    //右
    next = cur;
    next.col += 1;

来到这个位置之后，我们就已经将本题中的代码：

bool GetMazePath(int** maze, int n, int m, position cur)

中除了有关栈的使用以外的内容给讲完了，此时我们就要开始最让人头痛的递归回溯的过程的代码讲解了。

bool GetMazePath(int** maze, int n, int m, position cur)
{
    //上
    next = cur;
    next.row -= 1;
  if (IsPass(maze, n, m, next))
  {
    GetMazePath(maze, n, m, next);
  }
    //下
    next = cur;
    next.row += 1;
  if (IsPass(maze, n, m, next))
  {
    GetMazePath(maze, n, m, next);
  }
    //左
    next = cur;
    next.col -= 1;
  if (IsPass(maze, n, m, next))
  {
    GetMazePath(maze, n, m, next);
  }
    //右
    next = cur;
    next.col += 1;
  if (IsPass(maze, n, m, next))
  {
    GetMazePath(maze, n, m, next);
  }

此时可以看出我的上述代码就是一个通过上一个位置来找此时这个位置上下左右的位置的代码和判断上下左右是否是通路（0和非0）的代码，并且我们不难看出我们是把这句用来实现一直走的代码GetMazePath(maze, n, m, next); 放在了我的if语句之中，所以我们的目的就是为了让上下左右的位置先要满足是通路的条件之后，我们才开始重新调用 GetMazePath(maze, n, m, next); 也就是实现一直调用一直走，所以只要是通路（0）我们就可以继续往下走，当不是通路（非0）的情况下，我们就不调用，然后程序继续执行，然后就可以依次对上下左右都给进行判断了。

但是此时代码按照上面这样写，我们的程序就出大问题了，就是假如我在一处通路位置处，此时的这个位置的通路又不止有一条通路而是有多条通路，但是这些通路中又只有一条是可以最终到达我的终点的位置，但是如果我不进行处理的话，假如按照上述代码的原理，我走进的是一条死路，最终就会导致我的死路的最后一个位置的上下左右都是非0，就会导致本来我这个迷宫是有通路的，只是你走错了，导致最后返回的是没找到出口这个结果，所以我们的代码是有问题的。

解决方法：就是每当我找到一条通路之后，我就不找了，然后此时通过神奇的回溯递归原理来实现当我找到的是死路的回溯和各个通路的判断唯一终点的问题

代码如下：

bool GetMazePath(int** maze, int n, int m, position cur)
{
    //上
    next = cur;
    next.row -= 1;
  if (IsPass(maze, n, m, next))
  {
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
    //下
    next = cur;
    next.row += 1;
  if (IsPass(maze, n, m, next))
  {
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
    //左
    next = cur;
    next.col -= 1;
  if (IsPass(maze, n, m, next))
  {
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
    //右
    next = cur;
    next.col += 1;
  if (IsPass(maze, n, m, next))
  {
    if (GetMazePath(maze, n, m, next))
    {
      return true;
    }
  }
}

此时这样写，我们就真的是把递归的精华给用出来了（如果不明白就参考坐标图来进行递归展开图的描画） 反正目的就是上述所说，回溯和找唯一出口。

———————————————————————————————————————————

解决了上述的两个问题，我们算是把如何迷宫问题的最大的问题，如何顺利的走出迷宫的问题给解决了。假如看到了这，赶紧奖励自己一朵小红花！刻不容缓！快马加鞭！

———————————————————————————————————————————

搞定了本质问题之后，我们着手一些其它的问题

例：我相信这里很多的同学使用的都是VS这个编译器，不管你用的是几几年的VS，我在这里告诉你，VS是都不允许定义变长数组的，那么此时就有同学会问，我应该如何定义一个不限定大小的二维数组呢？如果不会的话，这边有详细教学哦！不过我相信你们都是会的。并且此时就是涉及到一个与指针数组相关的知识。

动态开辟二维数组原理：就是开辟先开辟一个一维数组出来，但是此时这个一维数组中的数据类型不是int 也不是 char 而是 int* ，没错就是一个指针类型的数组，就像是装了一卡车炸弹的卡车的感觉有没有（反正这边我某明就联想到了），然后用这个数组中的指针再去指向我的一维数组。

所以不难想到我的第一个一维数组中有几个指针，就可以指向几个一维数组，也就表示有n个指针，我就有n个一维数组，然后我就有了一个二维数组了（因为二维数组本身就是由一位数组构成的）

文字图示：

一 -> 一维数组
维 -> 一维数组       =>这样我就开辟出来了一个二维数组了
数 -> 一维数组
组 -> 一维数组

动态开辟二维数组代码：

int main()
{
    int** maze = (int**)malloc(sizeof(int*) * n);
  for (int i = 0; i < n; i++)
  {
    maze[i] = (int*)malloc(sizeof(int) * m);
  }
}

*n表示的就是乘n，*m表示的就是乘m，因为我要用n行那就是有n个一维数组，每个数组m大小，就是表示m列。

———————————————————————————————————————————

思路来到这里我们就直接要开始讲我们的第二重要的问题了，应该返回通路的坐标呢？

这里我们就涉及到了与数据结构中栈有关的知识了

有的同学会问，为什么跟栈有关系呢？

这边我们做一个讲解：首先想象一下，我从maze[0][0] 的位置开始走，最后走到了出口，我是不是是正着走的啊，我们一步一步打印不就行了吗？但是你再想，其实还是那个老问题，讲了好几遍了，就是当我此时的某一个位置有不止一个通路的时候，我的正确的通路却只有一条，按照我的代码原理，我是要一条通路一条通路的去走，最终才可以找到有出口的那条通路，所以此时你就可以知道，我是会走到死路中去的，但是死路不是我要的，所以不可以打印，所以我要把这条死路的每一个坐标删除之后，我是不是才可以打印啊！但是我要如何去删除死路的每一个坐标呢？可以发现我一定要从后往前删，才可以在回溯的过程中将我的每一个死路坐标给全部删除。刚好后进先出，这就是数据结构中栈的神奇特性。所以这就是涉及到栈的原因。

但是此时如果我们用C语言去实现的话就会非常的麻烦，麻烦在C语言中是没有栈这个库函数的，需要我们自己去实现一个栈，所以此时不用我多说了，就是去实现一个栈出来供我们存放数据和删除数据。

数据结构中栈的实现代码：（如果有不懂的东西可以先去复习一下什么是栈和栈的具体实现）

typedef position STDataType;//此时我的栈中存放的不是一个整形，存放的是一个坐标，所以存放的类型是position
typedef struct Stack
{
  STDataType* data;
  int top;
  int capacity;
}Stack ,ST;
//弄完了结构体我们现在就要弄几个主要的接口函数
//函数的声明
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPopt(ST* ps);
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
//函数的实现
void StackInit(ST* ps)
{
  assert(ps);
  ps->data = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
//销毁
void StackDestory(ST* ps)
{
  free(ps->data);
  ps->data = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
//栈顶插入
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->capacity == ps->top)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->data = tmp;
    ps->capacity = newCapacity;
  }
  ps->data[ps->top] = x;
  ps->top++;
}
//栈顶删除
void StackPopt(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}
//寻找栈顶
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->data[ps->top - 1];
}
//判断栈是否为空
bool StackEmpty(ST* ps)
{
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  return ps->top;
}

typedef position STDataType;然后因为此时我的栈中存放的不是一个整形，存放的是一个坐标，所以存放的类型要改成position，这样才可以符合我的使用。

有了这个栈，我们就可以很好的解决上述的那个删除死路数据的问题了，在GetMazePath()函数的头位置放上一个栈的输入，在尾位置放上一个栈的删除，因为代码太长的原因，我就不演示了，直接讲解就行，例如：此时根据回溯原理和递归展开图等多方面的想象，我可以知道，什么时候会开始我的回溯，显然是在我四个方向的位置都是非0的情况下，我就会开始回溯，但是如果我此时在GetMazePath() 函数的尾位置放了一个栈的删除，当我进行判断，发现四个位置都走不通的时候，此时就会随着程序的向下走，来到我的栈的删除的代码，此时执行一个栈的删除，刚好就可以把我最后录入的那个死路的最后一个位置的坐标给删除掉。同理删除别的位置的坐标，直到有找到通路开始递归。