搞到这里我们就已经把所有的问题给解决了，掌声鼓励！啪！啪！啪！啪！啪！啪！

剩下了最后一步已经不是问题了，就是一个普通的栈中元素的输出而已，只要把这个栈给输出，我们就获得了唯一的一条通路的坐标了，我们就搞定这个题目了。

代码如下：

void PrintPath(ST* path)//函数目的：输出栈里面的坐标
{
  //但是此时要怎么使用栈输出呢？
  //原理：使用两个栈，把我这个栈中的数据导入到另一个栈中，这样我就有了正的数据了，然后再出这个栈，就是就完成题意了
  //所以下述的代码就是为了：将我的path中的数据导入到rangePath中
  Stack rangePath;
  StackInit(&rangePath);
  while (!StackEmpty(path))
  {
    StackPush(&rangePath, StackTop(path));
    StackPopt(path);
  }
  while (!StackEmpty(&rangePath))
  {
    position top = StackTop(&rangePath);
    printf("(%d,%d)\n", top.row, top.col);
    StackPopt(&rangePath);
  }
  //销毁栈，好习惯
  StackDestory(&rangePath);
}

但是一提交我们发现，我们错了，为什么呢？说明我们的掌声是拍早了。

因为我们是把数据存到栈中，所以我们发现，想要从栈中拿数据拿的是后到前的，但是题意是前到后，所以我们就需要想上述代码一样，再建一个新的栈，把开头存放数据的栈中的数据导入到新的栈中，这样我们就实现了栈中的数据的顺序的调换，此时我们再把新栈中的数据输出，就发现大功告成了，是的，我们大功告成了。

但是这边我给到两个注意点：就是要注意栈的初始化和栈的销毁的同时记得将我们动态内存开辟出来的数组空间给释放掉

到这我们就可以宣布大功告成了！欧耶！耶耶耶耶耶！

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

当然身为一个贴心的博主，我肯定是会把完整的并且通过了全部测试用例的代码放在这里的，请放心啦！

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
typedef struct Position
{
  int row;
  int col;
}position;
//因为我要有一个栈来存放我的每一个通路的坐标位置，所以我要有一个栈
//栈的代码：
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;
}
/
//迷宫代码：
Stack path;
void PrintMaze(int** maze, int n, int m)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      printf("%d ", maze[i][j]);
    }
    printf("\n");
  }
}
void PrintPath(ST* path)//函数目的：输出栈里面的坐标
{
  //但是此时要怎么使用栈输出呢？
  //原理：使用两个栈，把我这个栈中的数据导入到另一个栈中，这样我就有了正的数据了，然后再出这个栈，就是就完成题意了
  //所以下述的代码就是为了：将我的path中的数据导入到rangePath中
  Stack rangePath;
  StackInit(&rangePath);
  while (!StackEmpty(path))
  {
    StackPush(&rangePath, StackTop(path));
    StackPopt(path);
  }
  while (!StackEmpty(&rangePath))
  {
    position top = StackTop(&rangePath);
    printf("(%d,%d)\n", top.row, top.col);
    StackPopt(&rangePath);
  }
  //销毁栈，好习惯
  StackDestory(&rangePath);
}
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)//就是限制范围和判断此时上下左右的数据是否是0,是0就可以通，否则就不行
  {
    return true;
    }
  else
  {
    return false;
  }
}
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;
}
int main()
{
  //有了上述的思路，开始吧！
  //1.输入两个数，弄一个数组出来
  int n = 0;
  int m = 0;
  while (scanf("%d%d", &n, &m) != EOF)//此时因为我可能有多组迷宫，所以我们这边要使用循环输入
  //scanf("%d%d", &n, &m);
  {
    //
// 动态开辟二维数组思路
// 
//int arr[n][m]; =>这个叫变长数组，但是vs不支持，有的新版编译器是支持的
//int arr[][] = { 0 };
//因为我的vs不支持变长数组，所以我们需要去动态开辟一个二维数组（此时就会涉及到指针数组的相关知识）
//为什么会涉及到指针数组的相关知识呢？
//原因就是，开辟数组时，不可以直接开辟二维数组，只能开辟一维数组，但是此时可以通过这个一维数组去指向别的一维数组（这样就可以类似的是开辟了一个二维数组了）
//图示：
//  一 -> 一维数组
//  维 -> 一维数组   =>这样我就开辟出来了一个二维数组了
//  数 -> 一维数组
//  组 -> 一维数组
// 
// 动态开辟二维数组代码
// 
//有了这个思路，开辟一个一维数组代码如下：
//int* arr = (int*)malloc(sizeof(int) * n);//此时就是说明我这个数组中有n个int类型的元素 （整形）
//有了开辟普通一维数组的思路，我们就可以模仿者开辟一个有n个指针的一维数组出来，所以开辟一个二维数组代码如下：
    int** maze = (int**)malloc(sizeof(int*) * n);//此时就是说明我这个数组中有n个int*类型的元素 （指针） =>  就是为了可以很好的指向我的其它的n个一维数组
    for (int i = 0; i < n; i++)
    {
      maze[i] = (int*)malloc(sizeof(int) * m);//此时就是让这个maze数组中的n个指针去指向我的m个开辟出来的二维数组
    }
    //开辟完二维数组就是拿来用的，所以现在要开始我的二维数组的输入了
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        scanf("%d", &maze[i][j]);//输入记得要取地址
      }
    }
  //  PrintMaze(maze, n, m);
    //2.寻找通路
    StackInit(&path);//此时一定要记得把我的栈给初始化一下，然后再去使用它
    position entry = { 0,0 };//将我的出发位置传上去，因为出发位置是一个二维的坐标（所以可以直接创建一个结构体来表示）
    if (GetMazePath(maze, n, m, entry))
    {
      PrintPath(&path);
    }
    else
    {
      printf("没有找到通路,要命\n");
    }
    //栈用完之后就是销毁，好习惯
    StackDestory(&path);
    //此时代码来到这个位置我们就要想到释放动态内存
    for (int i = 0; i < n; i++)
    {
      free(maze[i]);
    }
    free(maze);
    maze = NULL;
  }
  return 0;
}

2.迷宫进阶问题

题目我们直接贴图

还是上述的对于读题的理解，读题是很关键的，所以我们此时再研读一遍题目，然后明白题目中的几个主要问题

1. 用体力值P跳出这个地下迷宫

2. 一个n*m的迷宫

3. 0代表障碍物，1代表通路

4. 初始在(0,0)位置,出口在(0,m-1)

5. 一定有起点到终点可达的路径

6. 水平移动一个位置消耗1点体力值

7. 向上一个位置消耗3点体力值

8. 向下移动不消耗体力值

9. 体力值为0还没有出去表示出不去

本质其实还是一个初阶迷宫的问题，只不过是需要玩的东西变多了一点而已

例如：我们先思考一下体力值的问题，其实这个体力值的问题不就是在我判断上下左右的时候，同时也就可以实现吗？不是就当我把maze[0][0] 的上下左右的位置找出来之后，然后就可以对体力值进行加减了吗？所以明白了这个，我们就可以这样写。

首先在输入数值的时候多输入一个p给它，就代表着我的体力值。

例：while (scanf("%d%d", &n, &m, &p) != EOF)；

有了体力值之后，就把这个体力值当做一个参数传给别的函数使用，具体代码如下：

void GetMazePath(int** maze, int n, int m, position cur, int p)//第一个改进不要返回值
{
  StackPush(&path, cur);
  position next;
  maze[cur.row][cur.col] = 2;
  //上
  next = cur;
  next.row -= 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p - 3));//就是根据题意向上就是消耗3个体力值
  }
  //下
  next = cur;
  next.row += 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p));//向下就是不消耗
  }
  //左
  next = cur;
  next.col -= 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p - 1));//水平移动就是消耗一个
  }
  //右
  next = cur;
  next.col += 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p - 1));//水平移动就是消耗一个
  }
  maze[cur.row][cur.col] = 1;
  StackPopt(&path);
}

这样就很好的解决了我的体力值和我的上下左右的问题了

下面我们只需要把和通路和墙壁给改动一下和终点的位置给改动一下，我们的代码在迷宫这个层面上就没有什么大问题了，剩下的和迷宫问题关系都不是很大，涉及的更多的都是数据结构了。

改动通路和墙壁：

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] == 1)
  {
    return true;
  }
  else
  {
    return false;
  }
}

可以看出此时我的通路从0变成了1

改动终点：

void GetMazePath(int** maze, int n, int m, position cur, int p)
{
  StackPush(&path, cur);
  if (cur.row == 0 && cur.col == m - 1)
}

可以看出我将我的终点从右下角改成了右上角

此时我们进行了这几个地方的改进，会发现我们可以通过20%的测试用例了，这说明，我们的代码是朝着正确的方向进行的。

所以我们再把几个地方给处理一下，我们就搞定这个题目了

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

重大问题的改动

1. 第一个问题：

我们在做第一题的时候，我们是固定只需要有一条通路通过了就行了,但是此时的这个题目是要求我们把所有的通路都找出来，然后进行比较,比较出花费的体力最少的那一个才是我要的通路。

所以方法就是把所有的通路找出来，然后进行通路的花费体力的比较，就可以很好的解决本问题了

但是我们应该如何找出所有的通路并且找出最短的那条通路呢？我们此时就可以再一次的很好的利用栈的特性，我再重新创建一个新的栈，让之前的栈去找迷宫中的通路，然后把找到的通路复制到我的新的栈中，然后再让之前的那个栈去找通路，然后两条通路进行比较，把短的那条再一次的复制给我的新的栈，重复类推，直到找到最短的通路为止。代码如下：

void GetMazePath(int** maze, int n, int m, position cur, int p)//第一个改进不要返回值
{
  StackPush(&path, cur);
  if (cur.row == 0 && cur.col == m - 1)
  {
    if (p >= 0 && StackEmpty(&minPath) || StackSize(&path) < StackSize(&minPath))
    {
      //minPath = path  //这边切记不可以使用直接赋值的方式
      StackDestory(&minPath);
      //然后这里就会涉及到一个深拷贝问题了
      StackCopy(&path, &minPath);//类似strcopy
    }
  }
}

但是此时这个问题中的复制问题切记不可以直接使用赋值的方法（因为会涉及到一个深拷贝的问题）具体在下面讲到这个函数的时候进行讲解。

2. 第二个问题：

就是当我有两条通路有公共的通路的时候，此时第一条通路走完之后会把这条通路都给置成2，此时就会导致原来本来另一条通路也可以走，但是变成2之后，就不能走了，所以我们再走的过程中把1变成了2之后，要重新给它变回来，不然就会出问题，所以按照原理，就要把刚刚1改成2的地方给重新恢复成1。

所以我们要在这个void GetMazePath(int** maze, int n, int m, position cur, int p)，函数的尾位置放上一个maze[cur.row][cur.col] = 1; 的代码，就是表示把2恢复成1，只有恢复成1，我的下一条通路才可以也走成功，否则我就找不到所有的通路。

然后恢复完公共路径之后，我们来到第三个问题。

3.第三个问题：

涉及更新的问题

就是我的递归此时会把我的所有的通路都给走一遍，而在走一遍的过程中，每一次都会把这些通路的坐标给如到栈中去，所以如果不将栈进行一定的更新，此时我的栈中就会放着很多的东西

所以我们需要把栈进行更新，才可以实现，每一次栈中放的东西都是一条特定的通路而不是重复的通路

按照上述的代码，我是把路径记录在我的path中，所以我就是要对我的path进行更新就可以了

所以此时我就要给一个新的栈 Stack minPath; 来辅助我的 Stack path; 来进行我的栈的更新

if (StackEmpty(&minPath) || StackSize(&path) < StackSize(&minPath)) 此时就是表示我的minPath中还没有元素或者此时的path栈中的元素个数比minPath栈中的元素个数小（也就是通路的长短的判断），此时这两个条件成立一个都可以进到我的if语句之中

minPath = path; 但是这边切记不可以使用直接赋值的方式。因为如果直接赋值的话，就会涉及下面这两个问题了。

1.这样直接赋值会有内存泄露的风险,因为我是直接把我的path给给我的minPath，此时的原理的minPath的内存就会丢失

2.就是当我的path重新去找通路的时候，此时path会找到死路，找到死路本身是没有问题的，因为死路之后会回溯回来，回溯回来的过程中，会有删除的过程，在这个删除的过程之中就会出大问题

为什么呢？因为我把我的minPath直接赋值给path此时会使minPath和path指向的是同一块空间，然后在删除path的过程中，就会把我的minpath也给删除，所以就会有问题

解决方法：1.我要把minPath这个栈先给销毁掉 2.然后再进行拷贝：但是会涉及到一个深拷贝问题了

深拷贝：在销毁minPath的空间之后，重新开辟一个和path一样大的空间，然后再把path中的元素拷贝到minPath此时的这个独立空间之中就行了

如何拷贝呢？此时我们就再实现一个类似strcopy的StackCopy函数，然后再进行传址交换StackCopy(&path, &minPath); 代码如下：

void StackCopy(Stack* ppath, Stack* pminPath)
{
  pminPath->data = (STDataType*)malloc(sizeof(STDataType*) * ppath->capacity);
  memcpy(pminPath->data, ppath->data, sizeof(STDataType) * ppath->top);//直接将ppath中数据的值拷贝给pminPath（因为此时的空间的大小是一样的，所以不会出问题的）
  pminPath->top = ppath->top;
  pminPath->capacity = ppath->capacity;//此时这个位置就是叫做浅拷贝的问题
}

这个函数的意思就是先开辟一个和原栈相同大小的空间之后，再我接收原栈中的元素，然后还有top和capacity；

4. 第四个问题

此时代码来到这里，剩下的问题就是体力值的问题了

所以我们要把体力值的问题解决一下，解决方法就是当我的p不大于0的时候我就不会进行栈的更新，这样就可以很好的把体力值不够的那条通路给排除掉了

if (p >= 0 && StackEmpty(&minPath) || StackSize(&path) < StackSize(&minPath))

所以此时我们这种写法，体力值就只是用来判断我找的通路是有效的还是无效的而已，并没有直接和我的通路的长短挂钩

_____________________________________________________________________________

所以以上就是迷宫的进阶的题目，解释的效果可能没有初阶好，因为现在有点迟了，今天看了一下电视，然后导致写博客的时间有点紧了，所以请见谅！

当然细心的我，还是会把完整代码发出来的啦！

typedef struct Position
{
  int row;
  int col;
}position;
//因为我要有一个栈来存放我的每一个通路的坐标位置，所以我要有一个栈
//栈的代码：
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;
}
/
//迷宫代码：
Stack path;
//因为我每次都要更新我的栈，所以此时我就还要再给一个栈
Stack minPath;
void PrintMaze(int** maze, int n, int m)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      printf("%d ", maze[i][j]);
    }
    printf("\n");
  }
}
void PrintPath(ST* path)
{
  Stack rangePath;
  StackInit(&rangePath);
  while (!StackEmpty(path))
  {
    StackPush(&rangePath, StackTop(path));
    StackPopt(path);
  }
  while (StackSize(&rangePath) > 1)//此时这样写的目的就是为了控制最后一个不打印逗号而已，其它前面的Size-1个都需要打印逗号
  {
    position top = StackTop(&rangePath);
    printf("[%d,%d],", top.row, top.col);
    StackPopt(&rangePath);
  }
  position top = StackTop(&rangePath);
  printf("[%d,%d],", top.row, top.col);
  StackPopt(&rangePath);
  //销毁栈，好习惯
  StackDestory(&rangePath);
}
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] == 1)//就是限制范围和判断此时上下左右的数据是否是0,是0就可以通，否则就不行
  {
    return true;
  }
  else
  {
    return false;
  }
}
void StackCopy(Stack* ppath, Stack* pminPath)
{
  //StackInit(pminPath);//注意此时已经是指针了，不敢哪里都传地址
  //for (int i = 0; i < ppath->top; i++)//因为此时的ppath是一个指针所以可以使用->,而下面的cur只是一个结构体，所以不可以使用->,只能用 . =>来解引用
  //{
  //  StackPush(pminPath, ppath->data[i]);
  //}
  //此时除了上述的这种方法，还有就是下面这种更简单一些的方法
  pminPath->data = (STDataType*)malloc(sizeof(STDataType*) * ppath->capacity);
  memcpy(pminPath->data, ppath->data, sizeof(STDataType) * ppath->top);//直接将ppath中数据的值拷贝给pminPath（因为此时的空间的大小是一样的，所以不会出问题的）
  pminPath->top = ppath->top;
  pminPath->capacity = ppath->capacity;//此时这个位置就是叫做浅拷贝的问题
}
//bool GetMazePath(int** maze, int n, int m, position cur, int p)
void GetMazePath(int** maze, int n, int m, position cur, int p)//第一个改进不要返回值
{
  StackPush(&path, cur);
  if (cur.row == 0 && cur.col == m - 1)
  {
    //首先如果程序可以来到这里就是表示我已经找到了一条通路了
    //然后对通路进行判断
    //如果此时找到的通路比上一条通路更短，此时我就进行minPath的更新
    if (p >= 0 && StackEmpty(&minPath) || StackSize(&path) < StackSize(&minPath))//此时就是表示我的minPath中还没有元素或者此时的path栈中的元素个数比minPath栈中的元素个数小（也就是通路的长短的判断），此时这两个条件成立一个都可以进到我的if语句之中
    {
      //minPath = path  //这边切记不可以使用直接赋值的方式
      StackDestory(&minPath);
      //然后这里就会涉及到一个深拷贝问题了
      StackCopy(&path, &minPath);//类似strcopy
    }
  }
  position next;
  maze[cur.row][cur.col] = 2;
  //上
  next = cur;
  next.row -= 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p - 3));//就是根据题意向上就是消耗3个体力值
  }
  //下
  next = cur;
  next.row += 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p));//向下就是不消耗
  }
  //左
  next = cur;
  next.col -= 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p - 1));//水平移动就是消耗一个
  }
  //右
  next = cur;
  next.col += 1;
  if (IsPass(maze, n, m, next))
  {
    (GetMazePath(maze, n, m, next, p - 1));//水平移动就是消耗一个
  }
  //此时代码来到这里就是表示我找到了某一条通路，此时我按照原理，就要把刚刚1改成2的地方给重新恢复成2
  maze[cur.row][cur.col] = 1;//只有恢复成1，我的下一条通路才可以也走成功，否则我就找不到所有的通路
  StackPopt(&path);
}
int main()
{
  int n = 0;
  int m = 0;
  int p = 0;
  while (scanf("%d%d", &n, &m, &p) != EOF)
  {
    int** maze = (int**)malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++)
    {
      maze[i] = (int*)malloc(sizeof(int) * m);
    }
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        scanf("%d", &maze[i][j]);//输入记得要取地址
      }
    }
    PrintMaze(maze, n, m);
    //2.寻找通路
    StackInit(&path);
    StackInit(&minPath);//用了栈就一定要记得初始化
    position entry = { 0,0 };
    GetMazePath(maze, n, m, entry, p);
    if (!StackEmpty(&minPath))//此时就是表示我的栈有更新（有更新也就是说明我有找到更短的通路）
    {
      PrintPath(&minPath);
    }
    else//else就是表明我没有进行栈的更新，没有进行栈的更新也就是说明没有更短的通路，也就是说明我体力值不够，出不去
    {
      printf("Can not escape!\n");
    }
    StackDestory(&path);
    StackDestory(&minPath);//用了栈就要记得销毁
    for (int i = 0; i < n; i++)
    {
      free(maze[i]);
    }
    free(maze);
    maze = NULL;
  }
  return 0;
}

总结

所以以上就是这篇博客的所有内容了，其实我们主要还是学习思想，别的都好说，所以咱们不着急，慢慢来，一题一题的来。See you ！

数据结构中【迷宫问题】的两个OJ题2

2.迷宫进阶问题

总结

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构中【迷宫问题】的两个OJ题2

2.迷宫进阶问题

总结

热门文章

最新文章

相关课程

相关电子书