【C数据结构】迷宫问题

文章目录

• • 一、迷宫问题的思路
  • 二、简单迷宫的代码实现
  • 三、地下迷宫问题的思路
  • 四、地下迷宫的代码实现

前言:本章记录作者学习中，遇到的两个比较有趣的问题，一个简单和一个较复杂的迷宫问题。

一、迷宫问题的思路

让我们先来看简单的：迷宫问题
它的具体要求：

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

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

要求输出 如：

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

这道题的重点有：只能上下左右走，不能斜着走；左上角为起点，右下角为终点；只有唯一解。

思路分析：

1. 对于不支持变长数组的C版本来说，如果需要实现二维变长数组的话，就需要动态开辟二维数组。
2. 每次需要对上下左右四个方向进行判断，才能到达下一个坐标，并且如果四个方向都不能走而且还没到达终点，那么就要往回走。
3. 为了判断往回是否还有其它能走的方向，我们需要对走过的坐标进行标记，这样就不会出现走重复的路线。
4. 在结束的时候，我们需要打印这条路径的每个坐标，那么我们就需要对我们走过的坐标进行储存，对到达不了终点的路上的坐标消除，所以似乎需要栈来帮我们储存这个坐标。

二、简单迷宫的代码实现

动态实现二维变长数组：

先创建一个二维指针，储存N个一维指针的地址，这些一维指针都分别指向一个开辟了M个数据的数组

#includevoid 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");}}int main(){int N = 0, M = 0;scanf("%d %d", &N, &M);//动态开辟二维数组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);//测试是否能打印，看看有没有问题for (int i = 0; i < N; i++){free(maze[i]);}free(maze);return 0;}

四个方向判断的实现：
为了方便操作，我们建立一个结构体类型，方便定义坐标。

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

并且在测试页定义初始变量：

PT cur = { 0,0 };

1. 从（0，0）坐标开始，假设先判断上下，再判断左右，如果能通过就移动坐标，并且进入下次判断，直到到达终点，或者不能移动，并且需要对每次到达的坐标进行标记，假设标记为2.
2. 如果四个方向都不能走，并且没到达终点，那么将一直返回上一个位置，直到有其它方向能走。
3. 如果到达终点，返回true，直到跳出所有递归。

//判断下一个坐标是否能通过bool IsPass(int** maze, int N, int M, PT cur){if (cur.col >= 0 && cur.col < M && cur.row >= 0 && cur.row < N&& maze[cur.row][cur.col] == 0){return true;}else{return false;}}bool GetPath(int** maze, int N, int M, PT cur){//到达终点if (cur.row == N - 1 && cur.col == M - 1){return true;}//上下左右判断PT next;maze[cur.row][cur.col] = 2;//标记//上next = cur;next.row -= 1;if (IsPass(maze, N, M, next)){//上方向可以通过就移动到上方向的坐标，并且继续判断四个方向是否可以移动if (GetPath(maze, N, M, next)){//1.只有到达终点才会进入这次判断，并且一直返回true，直到退出所有递归。//2.因为这题只有唯一解，所以一旦找到终点就可以直接返回。return true;}}//下next = cur;next.row += 1;if (IsPass(maze, N, M, next)){if (GetPath(maze, N, M, next)){return true;}}//左next = cur;next.col -= 1;if (IsPass(maze, N, M, next)){if (GetPath(maze, N, M, next)){return true;}}//右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){if (GetPath(maze, N, M, next)){return true;}}//四个方向都不能走，就返回false，跳到上一个坐标判断它剩下的其它方向是否可以走return false;}

利用栈记录坐标的实现：
因为C语言没有自己的栈，所以我们还需要自己搭建一个栈。
栈的实现

1. 每次判断坐标前，先将当前坐标存入栈中，如果四个方向都不能走的时候，再出栈。
2. 当到达终点，返回完后，对栈中数据进行处理。
3. 因为栈中数据打印后与题目要求的打印相反，所有需要再创建一个栈，将当前栈中的数据导入另一个栈中，从而实现相反的打印。

完整代码：

#include;#include;#include;#include;typedef struct position{int row;int col;}PT;typedef PT STDataType;typedef struct stack {STDataType* a;int top;int capacity;}ST;void StackInit(ST*ps);void StackDestroy(ST* ps);void StackPush(ST* ps, STDataType x);void StackPop(ST* ps);STDataType StackTop(ST* ps);int StackSize(ST* ps);bool StackEmpty(ST* ps);//void StackInit(ST* ps) {ps->a = NULL;ps->capacity = 0;ps->top = 0;//或者-1}void StackPush(ST* ps, STDataType x) {if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 " />
 
 
记录重点：
 
  
现在0代表障碍物，1代表通路，并且增加了体力值，左右移动减1，上移动减3，下移动不消耗，如果体力值为0还未到达出口，将无法逃离迷宫。
（0，0）位置为起点，（0，m-1）位置为出口，并且现在要求最后打印的是最短路径。
体力值为0还未到达出口，结果需要打印：Can not escape!
坐标打印改变变成[0,0],
 
 
分析思路：
 
  
增加体力值P变量，并且当判断四个方向分别可以通过时，同时传入参数P，向上方向能通过传参数P-3，向左或者右方向能通过传P-1，向下传P；同时改变通路为1，出口为（0，m-1）
为了找到最短路径，直接通过建两个栈，一个记录当前路径的坐标，一个记录当前为止最短路径的坐标；利用递归列出所有可以走的路径，然后挑出最小的路径。（下面会重点介绍如何安全的转移栈以及如何用递归找到所有路径）
挑选的路径也要满足体力值条件；当所有的路径，体力都会耗尽且没有到达终点，记录最短路径坐标的栈为空，就可以通过这个情况打印Can not escape!。
 
 
四、地下迷宫的代码实现
 
先搭建一个基本的框架。
 
动态创建二维数组
获得路径
打印路径
 
创建体力值，并且改变通路条件、出口、打印和函数参数调用
 
//ST path;//可以创局部变量，这里方便一下bool IsPass(int** maze, int N, int M, PT cur){if (cur.col >= 0 && cur.col < M && cur.row >= 0 && cur.row < N&& maze[cur.row][cur.col] == 1) //通路条件为1{return true;}else{return false;}}bool GetPath(int** maze, int N, int M, PT cur, int P){//走过的坐标先入栈StackPush(&path, cur);//到达终点if (cur.row == 0 && cur.col == M - 1) //终点为(0,m-1){return true;}//上下左右判断PT next;maze[cur.row][cur.col] = 2;//上next = cur;next.row -= 1;if (IsPass(maze, N, M, next)){if (GetPath(maze, N, M, next, P-3)){return true;}}//下next = cur;next.row += 1;if (IsPass(maze, N, M, next)){if (GetPath(maze, N, M, next, P)){return true;}}//左next = cur;next.col -= 1;if (IsPass(maze, N, M, next)){if (GetPath(maze, N, M, next, P-1)){return true;}}//右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){if (GetPath(maze, N, M, next, P-1)){return true;}}//四个方向都不能走，就出栈返回StackPop(&path);return false;}void PrintPath(ST* ps){ST rpath;StackInit(&rpath);while (!StackEmpty(ps)){StackPush(&rpath, StackTop(ps));StackPop(ps);}while (StackSize(&rpath) > 1){PT cur = StackTop(&rpath);printf("[%d,%d],", cur.row, cur.col);StackPop(&rpath);}//前面打印带"," 最后一个不带PT cur = StackTop(&rpath);printf("[%d,%d]\n", cur.row, cur.col);StackPop(&rpath);StackDestroy(&rpath);}int main(){int N = 0, M = 0, P = 0; //体力值Pscanf("%d %d %d", &N, &M, &P);PT cur = { 0,0 };StackInit(&path);//动态开辟二维数组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]);}}if (GetPath(maze, N, M, cur, P)){PrintPath(&path);}StackDestroy(&path);for (int i = 0; i < N; i++){free(maze[i]);}free(maze);return 0;}
找到所有的路径和记录的实现：
 主要难的是这里的递归思想。
如果有通路，就移动到下一个坐标进行四个方向的判断，直到体力值用完到达终点或者没有到达终点。
到达终点之后，第一次到达终点保存这条路径，之后比较两条路径，选最短的路径；之后回到上一个坐标点
到达终点之后，当前坐标继续进行四个方向的判断，当四个方向都不能通过的时候，为了让下次能访问这个坐标，将这个坐标恢复为1，并且返回上一个坐标。
每个可以通过的坐标都将进行4个方向的判断，当所有可通过坐标判断完成，递归函数结束。
为什么要创建两个栈？
 因为有一个栈里面的数据是会变的，所有需要深拷贝一个栈记录原来不变的数据。
void StackCopy(ST* path, ST* minpath){minpath->a = (STDataType*)malloc(sizeof(STDataType*) * path->capacity);memcpy(minpath->a, path->a, sizeof(STDataType) * path->top);minpath->capacity = path->capacity;minpath->top = path->top;}void GetPath(int** maze, int N, int M, PT cur, int P){StackPush(&path, cur);//到达终点if (cur.row == 0 && cur.col == M - 1){if (P >= 0 && StackEmpty(&minpath) || StackSize(&path) < StackSize(&minpath)){StackDestroy(&minpath);StackCopy(&path, &minpath);}}//上下左右判断PT next;maze[cur.row][cur.col] = 2;//上next = cur;next.row -= 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P - 3);}//下next = cur;next.row += 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P);}//左next = cur;next.col -= 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P - 1);}//右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P - 1);}//恢复maze[cur.row][cur.col] = 1;StackPop(&path);}
完整代码：
#include;#include;#include;#include;#include;typedef struct position{int row;int col;}PT;typedef PT STDataType;typedef struct stack {STDataType* a;int top;int capacity;}ST;void StackInit(ST* ps);void StackDestroy(ST* ps);void StackPush(ST* ps, STDataType x);void StackPop(ST* ps);STDataType StackTop(ST* ps);int StackSize(ST* ps);bool StackEmpty(ST* ps);void StackInit(ST* ps) {ps->a = NULL;ps->capacity = 0;ps->top = 0;//或者-1}void StackPush(ST* ps, STDataType x) {if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if (tmp == NULL) {printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top++] = x;}void StackDestroy(ST* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}void StackPop(ST* ps){assert(ps);/*assert(ps->top > 0);*/assert(!StackEmpty(ps));ps->top--;}STDataType StackTop(ST* ps){assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];}int StackSize(ST* ps){assert(ps);return ps->top;}bool StackEmpty(ST* ps){return ps->top == 0;}void StackCopy(ST* path, ST* minpath){minpath->a = (STDataType*)malloc(sizeof(STDataType*) * path->capacity);memcpy(minpath->a, path->a, sizeof(STDataType) * path->top);minpath->capacity = path->capacity;minpath->top = path->top;}ST path;ST minpath;//判断通路bool IsPass(int** maze, int N, int M, PT cur){if (cur.col >= 0 && cur.col < M && cur.row >= 0 && cur.row < N&& maze[cur.row][cur.col] == 1){return true;}else{return false;}}//递归找到最小路径void GetPath(int** maze, int N, int M, PT cur, int P){StackPush(&path, cur);//到达终点if (cur.row == 0 && cur.col == M - 1){if (P >= 0 && StackEmpty(&minpath) || StackSize(&path) < StackSize(&minpath)){StackDestroy(&minpath);StackCopy(&path, &minpath);}}//上下左右判断PT next;maze[cur.row][cur.col] = 2;//上next = cur;next.row -= 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P - 3);}//下next = cur;next.row += 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P);}//左next = cur;next.col -= 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P - 1);}//右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){GetPath(maze, N, M, next, P - 1);}maze[cur.row][cur.col] = 1;StackPop(&path);}//打印坐标void PrintPath(ST* ps){ST rpath;StackInit(&rpath);while (!StackEmpty(ps)){StackPush(&rpath, StackTop(ps));StackPop(ps);}while (StackSize(&rpath) > 1){PT cur = StackTop(&rpath);printf("[%d,%d],", cur.row, cur.col);StackPop(&rpath);}PT cur = StackTop(&rpath);printf("[%d,%d]\n", cur.row, cur.col);StackPop(&rpath);StackDestroy(&rpath);}int main(){int N = 0, M = 0, P = 0;scanf("%d %d %d", &N, &M, &P);PT cur = { 0,0 };StackInit(&path);StackInit(&minpath);//动态开辟二维数组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]);}}//获得最小路径GetPath(maze, N, M, cur, P);if (!StackEmpty(&minpath)){PrintPath(&minpath);}else{printf("Can not escape!");}StackDestroy(&path);StackDestroy(&minpath);for (int i = 0; i < N; i++){free(maze[i]);}free(maze);return 0;}
总结：迷宫问题的难点主要是怎么找到路径，如何打印路径坐标。如果能解决这些问题，那么对递归的理解以及栈的应用有很大的提升。