🍬个人主页：Yanni.—
🌈数据结构：Data Structure.
🎂C语言笔记：C Language Notes
🏀OJ题分享： Topic Sharing
前言：
在笔试或者竞赛的过程中，经常会遇到迷宫问题，今天用c语言给大家带来初入迷宫的思路，以及一些复杂条件增加的迷宫问题，相信大家看完之后会收获满满！
基础迷宫
迷宫问题__牛客网 (nowcoder.com)
这道OJ题曾经是百度某一年的其中一个笔试题，迷宫问题的本质就是一个图遍历问题，从起点开始不断四个方向探索，直到走到出口，走的过程我们可以借助数据结构-栈来记录走过路径的坐标。
栈记录坐标有两方面的作用：
1.记录走过的路径
2.便于走到死路时进行回溯找其他的通路
创建迷宫
我们把迷宫想象成xy坐标轴上的坐标，创造出一个二维数组，考虑到空间需要自己输入，所以我们这里开辟动态二维数组，要开辟动态二维数组，有两个操作。
1.创造指针数组
2.在指针数组的基础上开辟动态数组空间
typedef struct postion
{int row;int col;
}PT;
int main()
{int N = 0, M = 0;while (scanf("%d%d", &N, &M) != 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]);}}PtintMaze(maze, N, M);StackInit(&path);PT entry = { 0,0 };if (GetMazePath(maze, N, M, entry)){PrintPath(&path);}else {printf("没有找到通路");}StackDestory(&path);//二维数组的销毁for (int i = 0; i < N; i++){free(maze[i]);}free(maze);maze = NULL;}return 0;
}
//打印迷宫
void PtintMaze(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");}printf("\n");
}上面结构体定义了xy坐标，然后再开辟动态二维数组。
回溯算法
接下来解题。要从起始位置到达终点，不免会遇到死路，遇到就必须往回走，看回去的路有没有可以走的方向，所以大致思路为：
1.将每个坐标都需要进行四个方向的判断，可以走，那就走到下一个，将原来的0变成2，代表已经走过
2.遇到思路，往回走，再去判断之前的路的方向，可以走，就继续。
3.重复上面的操作，直到走到终点。
bool GetMazePath(int** maze, int N, int M, PT cur)
{//压栈StackPush(&path, cur);//判断是否到达终点if (cur.row == N - 1 && cur.col == M - 1){return true;}PT next;maze[cur.row][cur.col] = 2;//将走过的路改为2//上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;}}StackPop(&path);return false;
}用bool类型来接收返回值，进行回溯。
下面是判断是否可以走的代码段
bool IsPass(int** maze, int N, int M, PT pos)
{if (pos.col >= 0 && pos.col < N&& pos.row >= 0 && pos.row < M&& maze[pos.row][pos.col] == 0){return true;}else {return false;}
}打印路径坐标
路径坐标的打印就需要用到数据结构-栈（后进先出）了，将走过的路径储存再栈中，再通过倒栈的方法拿出来，这样迷宫的通路就打印出来了。（栈的实现在前面的博客已经讲过了，不懂的可以取看噢）
//打印路径坐标
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);}StackDestory(&rpath);
}创造一个新的栈，将储存路径的栈的数据给进去，这样原本倒着的顺序变成顺序了。
复杂迷宫
这里并不是迷宫的复杂，而是条件的复杂，新增加了两个条件。
1.要算出迷宫的最短路径。
2.往下走会消耗三个体力值，其他方向只消耗一个体力值，判断在规定的体力值的情况下能否走出迷宫。
思路分析
这是两种走出迷宫的通路，按照基础迷宫的方法，会出现第一种图的情况。接下来我们要在基础迷宫的基础上改动功能，使得出现第二种图的情况。
1.我们要创造两个栈，一个栈minpath用来存放最小的路径，另一个栈path用来进行实验 。
2.这里的栈拷贝涉及到浅拷贝和深拷贝的问题。
3.体力值可以用一个变量来表示。
回溯算法的改进
1.这里我们需要找到所有的通路，再将这些通路中最小的路径选出来，可以先将第一个通路放进minpath中，之后的通路存放在path中，两者进行比较，path>minpath，则minpath不变，反之，将path的路径拷贝到minpath当中。
2.要实现找到所有的通路，则不需要接收返回值，函数类型为void。
3.在找路的过程中，往回走时，要将走过的路变成障碍值，这样就可以寻找其他的路。
//回溯算法进行找路
void GetMazePath(int** maze, int N, int M, PT cur,int p)
{//压栈StackPush(&path, cur);//判断是否到达终点if (cur.row == 0 && cur.col == M - 1){//找到了更短的路径，更新minpathif (p>0 && StackEmpty(&minpath) || StackSize(&minpath) > StackSize(&path)){StackDestory(&minpath);StackCopy(&path, &minpath);}}PT 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);}//下next = cur;next.row += 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);}//右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){GetMazePath(maze, N, M, next,p-1);}maze[cur.row][cur.col] = 0;StackPop(&path);
}深拷贝与浅拷贝
在比较的过程中，会发生拷贝的算法，这里必须使用深拷贝，否则会发生越界访问的情况。
浅拷贝：仅仅将栈path里的坐标赋值到栈minpath当中，空间大小并没有改变。
深拷贝：需要将minpath里的空间释放，再创造出和栈path空间大小一样的空间，再将栈path里的值拷贝到栈minpath里面。
//深度拷贝 如果是进行浅度拷贝会发生越界访问
void StackCopy(Stack* ppath, Stack* pcopy)
{pcopy->a = (STDataType*)malloc(sizeof(STDataType*) * ppath->capacity);if (pcopy->a == NULL){perror("malloc fail");}memcpy(pcopy->a, ppath->a, sizeof(STDataType*) * ppath->top);pcopy->top = ppath->top;pcopy->capacity = ppath->capacity;
}总代码实现
Text.c
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include"Stack.h"
#include<string.h>Stack path;
Stack minpath;
//打印迷宫
void PtintMaze(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");}printf("\n");
}
//判断是否可以走
bool IsPass(int** maze, int N, int M, PT pos)
{if (pos.col >= 0 && pos.col < N&& pos.row >= 0 && pos.row < M&& maze[pos.row][pos.col] == 0){return true;}else {return false;}
}//打印路径坐标
void PrintPath(Stack* ps)
{//将path的数据倒到rpathStack rpath;StackInit(&rpath);while (!StackEmpty(ps)){StackPush(&rpath, StackTop(ps));StackPop(ps);}while (StackSize(&rpath)>1){PT top = StackTop(&rpath);printf("(%d,%d)\n", top.row, top.col);StackPop(&rpath);}PT top = StackTop(&rpath);printf("(%d,%d)\n", top.row, top.col);StackPop(&rpath);StackDestory(&rpath);
}
//深度拷贝 如果是进行浅度拷贝会发生越界访问
void StackCopy(Stack* ppath, Stack* pcopy)
{pcopy->a = (STDataType*)malloc(sizeof(STDataType*) * ppath->capacity);if (pcopy->a == NULL){perror("malloc fail");}memcpy(pcopy->a, ppath->a, sizeof(STDataType*) * ppath->top);pcopy->top = ppath->top;pcopy->capacity = ppath->capacity;
}//回溯算法进行找路
void GetMazePath(int** maze, int N, int M, PT cur,int p)
{//压栈StackPush(&path, cur);//判断是否到达终点if (cur.row == 0 && cur.col == M - 1){//找到了更短的路径，更新minpathif (p>0 && StackEmpty(&minpath) || StackSize(&minpath) > StackSize(&path)){StackDestory(&minpath);StackCopy(&path, &minpath);}}PT 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);}//下next = cur;next.row += 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);}//右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){GetMazePath(maze, N, M, next,p-1);}maze[cur.row][cur.col] = 0;StackPop(&path);
}int main()
{int N = 0, M = 0, P = 0;while (scanf("%d%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]);}}PtintMaze(maze, N, M);StackInit(&path);StackInit(&minpath);PT entry = { 0,0 };GetMazePath(maze, N, M, entry,P);if (!StackEmpty(&minpath)){PrintPath(&minpath);}else {printf("没有找到通路");}StackDestory(&path);StackDestory(&minpath);//二维数组的销毁for (int i = 0; i < N; i++){free(maze[i]);}free(maze);maze = NULL;}return 0;
}Stack.h
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
//创造坐标
typedef struct postion
{int row;int col;
}PT;
typedef PT STDataType;typedef struct Stack
{ STDataType* a;int top; //栈顶int capacity;//栈容量
}Stack;
//初始化栈
void StackInit(Stack* ps);
//栈的销毁
void StackDestory(Stack* ps);
//压栈
void StackPush(Stack* ps,STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素的个数
int StackSize(Stack* ps);
//检查栈是否为空，如果不为空则返回0，如果为空则返回非零结果
bool StackEmpty(Stack* ps);//bool也可以使用 表示真假
Stack.c
#include"Stack.h"void StackInit(Stack* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);ps->top = 0;ps->capacity = 4;
}
void StackDestory(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;}
//入栈
void StackPush(Stack* ps,STDataType x)
{assert(ps);if (ps->top == ps->capacity)//考虑到空间大小不够，使用realloc进行增容操作{STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));if (tmp == NULL)//要注意tmp可能为空的情况。{printf("realloc fail!!!");exit(-1);}ps->a = tmp;//别忘了把指针a指向新开辟的空间ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;//注意个数的增加
}
void StackPop(Stack* ps)
{assert(ps);assert(ps->top > 0);//top不能小于或等于0，因为top是指向栈顶元素的下一个位置ps->top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];//因为top是指向栈顶元素的下一个位置，所以要-1}
int StackSize(Stack* ps)
{assert(ps);return ps->top;}
bool StackEmpty(Stack* ps)//bool也可以使用 表示真假
{assert(ps);return ps->top == 0;
}好啦，这就是今天学习的分享啦！看到希望大家的三连呀！
如果有不当之处，欢迎大佬指正！
