一. 题目描述

牛客网链接：https://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc

二. 思想

2.1 算法—回溯算法

• 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

• 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

• 许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。（深度优先遍历，能走则走，不能走则退）
  

2.2 思路分析+图解

• 对于不支持变长数组的C版本来说，如果需要实现二维变长数组的话，就需要动态开辟二维数组。

• 每次需要对上下左右四个方向进行判断（但是四个方向选择的先后顺序不是很重要，每个迷宫不一样），才能到达下一个坐标，并且如果四个方向都不能走而且还没到达终点，那么就要往回走。

• 为了判断往回是否还有其它能走的方向，我们需要对走过的坐标进行标记（已走过的坐标，用数字 2 标记），这样就不会出现走重复的路线。

• 在结束的时候，我们需要打印这条路径的每个坐标，那么我们就需要对我们走过的坐标进行储存，对到达不了终点的路上的坐标消除，所以似乎需要栈来帮我们储存这个坐标。

三. 代码实现

3.1 二维数组的实现

void PrintMase(int** mase, int N, int M)
{for (int i = 0;i < N;i++)//先确定行---一维数组{for (int j = 0;j < M;j++){printf("%d ", mase[i][j]);}printf("\\n");}
}

3.2 上下左右四个方向的判断

• 从（0，0）坐标开始，假设先判断上下，再判断左右，如果能通过就移动坐标，并且进入下次判断，直到到达终点，或者不能移动，并且需要对每次到达的坐标进行标记，假设标记为2。

• 如果四个方向都不能走，并且没到达终点，那么将一直返回上一个位置，直到有其它方向能走。

• 如果到达终点，返回true，直到跳出所有递归。

bool GetMasePath(int** maze, int N, int M)
{StackPush(&path, cur);//cur表示当前坐标if (cur.row == N - 1 && cur.col == M - 1)//当前坐标为右下时，走出迷宫{return true;}//走过的标志为2PT next;maze[cur, row][cur.col] == 2;//上next = cur;next.row -= 1;//行减1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}//下next = cur;next.row += 1;//行加1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}//左next = cur;next.col -= 1;//列减1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}//右next = cur;next.col += 1;//列加1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}
}

3.4 用栈记录坐标的实现

由于C语言没有自己的栈，所以要自己搭建一个栈。

• 每次判断坐标前，先将当前坐标存入栈中，如果四个方向都不能走的时候，再出栈。

• 当到达终点，返回完后，对栈中数据进行处理。

• 因为栈中数据打印后与题目要求的打印相反，所有需要再创建一个栈，将当前栈中的数据导入另一个栈中，从而实现相反的打印。

为什么要建立两个栈？

因为题目要求的打印路径顺序是有先后的，只有一个栈是，路径坐标是倒的，与题目要求相反；所以建立两个栈，使得坐标顺序不变

typedef PT STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;//空间
}ST;void StackInit(ST* ps);
void StackDestory(ST* ps);void StackPush(ST* ps, STDataType x);//入栈
void StackPop(ST* ps);//出栈STDataType StackTop(ST* ps);//返回栈顶元素int StackSize(ST* ps);//栈大小bool StackEmpty(ST* ps);//bool 判断是否栈空，栈空为1//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//初次分配if (ps->a == NULL){printf("malloc fail\\n");exit(-1);}ps->capacity = 4;ps->top = 0;
}//销毁栈
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType)realloc(ps->a, ps->capacity);//再分配if (tmp == NULL){printf("realloc fail\\n");exit(-1);//为假，退出}else{ps->a = tmp;ps->capacity *= 2;}}ps->a[ps->top] = x;ps->top++;}//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}//返回栈顶
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);{return ps->a[ps->top - 1];}
}//栈大小
int StackSize(ST* ps)
{assert(ps);return ps->top;
}//判断栈空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}Stack path;
///打印迷宫
void PrintMase(int** mase, int N, int M)
{for (int i = 0;i < N;i++)//先确定行---一维数组{for (int j = 0;j < M;j++){printf("%d ", mase[i][j]);}printf("\\n");}
}//输出栈中坐标路径
void PrintPath(Stack* ps)
{//把path数据倒置入rPathStack rPath;StackInit(&rPath);while (!StackEmpty(&Path){StackPush(&rPath, StackTop(&Path));StackPop(&path)}while (!StackEmpty(&rPath){PT top = StackTop(&rPath);printf("(%d , %d)\\n", top.row, top.col);StackPop(&rpath)}
}//判读路径是否正确
bool IsPass(int** maze, int N, int M)
{if (pos.row >= 0 && pos.row < N && pos.col >= 0 && pos.col < M && masz[pos.row][pos.col] == 0){return true;}else{return false;}
}

3.5 完整代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef struct Postion
{int row;int col;
}PT;
//typedef PT STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;//空间
}ST;void StackInit(ST* ps);
void StackDestory(ST* ps);void StackPush(ST* ps, STDataType x);//入栈
void StackPop(ST* ps);//出栈STDataType StackTop(ST* ps);//返回栈顶元素int StackSize(ST* ps);//栈大小bool StackEmpty(ST* ps);//bool 判断是否栈空，栈空为1//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//初次分配if (ps->a == NULL){printf("malloc fail\\n");exit(-1);}ps->capacity = 4;ps->top = 0;
}//销毁栈
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType)realloc(ps->a, ps->capacity);//再分配if (tmp == NULL){printf("realloc fail\\n");exit(-1);//为假，退出}else{ps->a = tmp;ps->capacity *= 2;}}ps->a[ps->top] = x;ps->top++;}//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}//返回栈顶
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);{return ps->a[ps->top - 1];}
}//栈大小
int StackSize(ST* ps)
{assert(ps);return ps->top;
}//判断栈空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}Stack path;
///打印迷宫
void PrintMase(int** mase, int N, int M)
{for (int i = 0;i < N;i++)//先确定行---一维数组{for (int j = 0;j < M;j++){printf("%d ", mase[i][j]);}printf("\\n");}
}//输出栈中坐标路径
void PrintPath(Stack* ps)
{//把path数据倒置入rPathStack rPath;StackInit(&rPath);while (!StackEmpty(&Path){StackPush(&rPath, StackTop(&Path));StackPop(&path)}while (!StackEmpty(&rPath){PT top = StackTop(&rPath);printf("(%d , %d)\\n", top.row, top.col);StackPop(&rpath)}
}//判读路径是否正确
bool IsPass(int** maze, int N, int M)
{if (pos.row >= 0 && pos.row < N && pos.col >= 0 && pos.col < M && masz[pos.row][pos.col] == 0){return true;}else{return false;}
}//上下左右遍历
bool GetMasePath(int** maze, int N, int M)
{StackPush(&path, cur);//cur表示当前坐标if (cur.row == N - 1 && cur.col == M - 1)//当前坐标为右下时，走出迷宫{return true;}//走过的标志为2PT next;maze[cur, row][cur.col] == 2;//上next = cur;next.row -= 1;//行减1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}//下next = cur;next.row += 1;//行加1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}//左next = cur;next.col -= 1;//列减1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}//右next = cur;next.col += 1;//列加1if (IsPass(mzse, N, M, next)){if (GetMasePath(maze, N, M, next)){return true;}}
}int main()
{int N = 0, M = 0;while (scanf("%d%d", &N, &M) != EOF){// int a[n][m]; // vs2013 不支持// 动态开辟二维数组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]);}}StackInit(&path);// PrintMaze(maze, N, M);PT entry = { 0, 0 };if (GetMazePath(maze, N, M, entry)){//printf("找到通路\\n");PirntPath(&path);}else{printf("没有找到通路\\n");}StackDestory(&path);for (int i = 0; i < N; ++i){free(maze[i]);}free(maze);maze = NULL;}return 0;
}

四. 总结

迷宫问题的难点:

1. 建立两个栈，使得打印的顺序是正确的
2. 怎么找路径，标记已经走过的坐标
3. 栈的应用
4. 递归
5. 回溯算法

感谢阅读！