迷宫问题（地下迷宫）——II
前言：
这题是在昨天迷宫问题——I的基础上进行的变形，因此，如果昨天的题目没看或者对迷宫问题不怎么了解，建议先看看昨天的解析。
迷宫问题——I源代码：
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef struct Position { int row; int col; }POS; typedef POS StackDataType; typedef struct Stack { StackDataType* data; int top; }ST; ST STACK; //定义一个全局栈 //初始化栈 void StackInit(ST* stack) { stack->top = 0; stack->data = (POS*)malloc(sizeof(POS) * 100); } //判断栈空 bool StackEmpty(ST* stack) { return stack->top == 0; } //入栈 void StackPush(ST* stack, POS val) { stack->data[(stack->top)++] = val; } //出栈 void StackPop(ST* stack) { assert(!StackEmpty(stack)); stack->top--; } //返回栈顶元素 StackDataType StackTop(ST* stack) { return stack->data[stack->top - 1]; } //判断是否可以前进 bool Judge(int** nums, int n, int m, POS pos) { if (pos.col >= m || pos.col < 0 || pos.row >= n || pos.row < 0 || nums[pos.row][pos.col] != 0) { return false; } else return true; } //找路 bool FindWay(int** nums, int n, int m, POS entry) { //先将该位置入栈 StackPush(&STACK, entry); //判断是否已经到了出口 if(entry.row == n - 1 && entry.col == m - 1) return true; //为了防止走相同的路，要对走过的路做标记 nums[entry.row][entry.col] = -1; //上 POS next = entry; next.row--; if (Judge(nums, n, m, next)) { //如果到了出口，直接返回 if (FindWay(nums, n, m, next)) return true; } //下 next = entry; next.row++; if (Judge(nums, n, m, next)) { //如果到了出口，直接返回 if (FindWay(nums, n, m, next)) return true; } //左 next = entry; next.col--; if (Judge(nums, n, m, next)) { //如果到了出口，直接返回 if (FindWay(nums, n, m, next)) return true; } //右 next = entry; next.col++; if (Judge(nums, n, m, next)) { //如果到了出口，直接返回 if (FindWay(nums, n, m, next)) return true; } //如果是死路，就出栈，并返回假，说明没到出口 StackPop(&STACK); return false; } void PrintWay() { //创建一个辅助栈 ST* stack = (ST*)malloc(sizeof(ST)); StackInit(stack); //将原始栈的数据放入辅助栈 while (!StackEmpty(&STACK)) { POS temp = StackTop(&STACK); StackPop(&STACK); StackPush(stack, temp); } //打印辅助栈的路径 while (!StackEmpty(stack)) { POS temp = StackTop(stack); StackPop(stack); printf("(%d,%d)\n", temp.row, temp.col); } } int main() { int n, m; scanf("%d%d", &n, &m); //动态申请二维数组 int** nums = (int**)malloc(sizeof(int*) * n); for (int i = 0; i < n; i++) { nums[i] = (int*)malloc(sizeof(int) * m); } //输入 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &nums[i][j]); //初始化全局栈 StackInit(&STACK); //找路 POS entry = { 0,0 }; FindWay(nums, n, m, entry); //打印路径 PrintWay(); //释放动态空间 for(int i = 0; i < n; i++) free(nums[i]); free(nums); return 0; }
思路
总体来说，这题相较于昨天的迷宫问题——I，有以下几点的变化：
- 可以走的路变成了1，而0是不能走的路
- 出口由右下角变成了右上角
- 增加了体力值的概念，如果体力值不够到达出口，则不能逃离迷宫
- 如果不讨论体力值，那么可能有多条通向出口的路，但如果要看体力值，根据题意，则只存在(或不存在）一条路径，这涉及到了最短路径，因此我们必须要将所有可能的路径都求出来
- 最后打印路径的格式不同
在迷宫问题——I的基础上修改
由于问题2和问题2障碍物和可以到达的位置所代表的数据恰好相反，首先修改Judge()函数：
bool Judge(int** nums, int n, int m, POS pos) { if (pos.col >= m || pos.col < 0 || pos.row >= n || pos.row < 0 || nums[pos.row][pos.col] != 1) { return false; } else return true; }
出口的位置被修改，修改判断是否到达出口的条件：
if(P >= 0 && entry.row == 0 && entry.col == m - 1) { ……………… }
《迷宫问题——I》中，因为有效路径唯一，所以我们找到一条路就可以退出递归，直接打印路径了。而《迷宫问题——II》需要求最短路径，因此我们就必须先找出所有可能的路径，所以我们就不能找到一条路就退出函数，所以我们要将FindWay()的返回类型由bool改为void，到达出口也不要返回，同时要引入体力参数P
void FindWay(int** nums, int n, int m, POS entry, int P) { ……………… }
《迷宫问题——I》中，为避免回溯之后走相同的路，我们会将走过的路进行标记。但是到了《迷宫问题——II》，如果找完一条路后再找第二条路，如果之前的标记没有被消除，那么就不能继续找路了，因此在回溯的过程中，我们要将标记取消。
void FindWay(int** nums, int n, int m, POS entry, int P) { …………………… //上 …………………… //下 …………………… //左 …………………… //右 …………………… nums[entry.row][entry.col] = 1; }
找最短路径
要找到最短路径，我们只需要再创建一个栈MIN_STACK
- 如果
MIN_STACK为空，那么直接将找到的路径放入MIN_STACK中 - 如果不为空，那么就比较找到的路径的长度和
MIN_STACK存储路径的长度，如果新找到的路径要短，就先销毁MIN_STACK中的路径，再将新找到的路径放入 - 注意，如果到达出口时体力小于0，那么这条路径就是无效路径
if(P >= 0 && entry.row == 0 && entry.col == m - 1) //如果到达出口且体力值大于等于0 { if(StackEmpty(&MIN_STACK) || MIN_STACK.top > STACK.top) //如果MIN_STACK为空或者原最短路径长度大于新的长度 { StackDestory(&MIN_STACK); //先销毁原有数据 StackCopy(&MIN_STACK, &STACK); //进行数据拷贝 } }
FindWay实现
void FindWay(int** nums, int n, int m, POS entry, int P) { //将当前位置入栈 StackPush(&STACK, entry); //为防止走相同的路，给当前位置标记 nums[entry.row][entry.col] = -1; if(P >= 0 && entry.row == 0 && entry.col == m - 1) //如果到达出口且体力值大于等于0 { if(StackEmpty(&MIN_STACK) || MIN_STACK.top > STACK.top)//如果MIN_STACK为空或原最短路径长度大于新的长度 { StackDestory(&MIN_STACK); //先销毁原有数据 StackCopy(&MIN_STACK, &STACK); //进行数据拷贝 } } //上 POS next = entry; next.row--; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P - 3); } //下 next = entry; next.row++; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P); } //左 next = entry; next.col--; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P - 1); } //右 next = entry; next.col++; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P - 1); } //无路可走或者已经到达出口就回溯，继续找其他的路 //将当前位置出栈 StackPop(&STACK); //删除标记 nums[entry.row][entry.col] = 1; }
拷贝路径(StackCopy)
//将stack2的数据拷贝到stack1中 void StackCopy(ST* stack1, ST* stack2) { stack1->data = (StackDataType *)malloc(sizeof(StackDataType) * stack2->top); //创建相同大小的数组 memcpy(stack1->data, stack2->data, sizeof(StackDataType) * stack2->top); //拷贝数组 stack1->top = stack2->top; //拷贝大小 }
打印路径
void PrintWay() { ST* stack = (ST*)malloc(sizeof(ST)); StackInit(stack); while (!StackEmpty(&MIN_STACK)) { POS temp = StackTop(&MIN_STACK); StackPop(&MIN_STACK); StackPush(stack, temp); } //由于最后一个坐标的后面不要打印字符','，因此循环到倒数第二个坐标就停止，最后一个坐标单独打印 while (stack->top - 1) { POS temp = StackTop(stack); StackPop(stack); printf("[%d,%d],", temp.row, temp.col); } //最后一个坐标单独打印 POS temp = StackTop(stack); StackPop(stack); printf("[%d,%d]\n", temp.row, temp.col); }
实现代码：
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> #include <string.h> typedef struct Position { int row; int col; }POS; typedef POS StackDataType; typedef struct Stack { StackDataType* data; int top; }ST; ST STACK; ST MIN_STACK; //初始化栈 void StackInit(ST* stack) { stack->top = 0; stack->data = (POS*)malloc(sizeof(POS) * 100); } //判断栈空 bool StackEmpty(ST* stack) { return stack->top == 0; } //入栈 void StackPush(ST* stack, POS val) { stack->data[(stack->top)++] = val; } //出栈 void StackPop(ST* stack) { assert(!StackEmpty(stack)); stack->top--; } //返回栈顶元素 StackDataType StackTop(ST* stack) { return stack->data[stack->top - 1]; } //销毁栈 void StackDestory(ST *stack) { free(stack->data); stack->data = NULL; stack->top = 0; } //复制栈 void StackCopy(ST* stack1, ST* stack2) { stack1->data = (StackDataType *)malloc(sizeof(StackDataType) * stack2->top); memcpy(stack1->data, stack2->data, sizeof(StackDataType) * stack2->top); stack1->top = stack2->top; } //判断位置是否有效 bool Judge(int** nums, int n, int m, POS pos) { if (pos.col >= m || pos.col < 0 || pos.row >= n || pos.row < 0 || nums[pos.row][pos.col] != 1) { return false; } else return true; } //找路 void FindWay(int** nums, int n, int m, POS entry, int P) { //将当前位置入栈 StackPush(&STACK, entry); //为防止走相同的路，给当前位置标记 nums[entry.row][entry.col] = -1; if(P >= 0 && entry.row == 0 && entry.col == m - 1) //如果到达出口且体力值大于等于0 { if(StackEmpty(&MIN_STACK) || MIN_STACK.top > STACK.top)//如果MIN_STACK为空或原最短路径长度大于新的长度 { StackDestory(&MIN_STACK); //先销毁原有数据 StackCopy(&MIN_STACK, &STACK); //进行数据拷贝 } } //上 POS next = entry; next.row--; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P - 3); } //下 next = entry; next.row++; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P); } //左 next = entry; next.col--; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P - 1); } //右 next = entry; next.col++; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next, P - 1); } //无路可走或者已经到达出口就回溯，继续找其他的路 //将当前位置出栈 StackPop(&STACK); //删除标记 nums[entry.row][entry.col] = 1; } //打印路径 void PrintWay() { ST* stack = (ST*)malloc(sizeof(ST)); StackInit(stack); while (!StackEmpty(&MIN_STACK)) { POS temp = StackTop(&MIN_STACK); StackPop(&MIN_STACK); StackPush(stack, temp); } //由于最后一个坐标的后面不要打印字符','，因此循环到倒数第二个坐标就停止，最后一个坐标单独打印 while (stack->top - 1) { POS temp = StackTop(stack); StackPop(stack); printf("[%d,%d],", temp.row, temp.col); } //最后一个坐标单独打印 POS temp = StackTop(stack); StackPop(stack); printf("[%d,%d]\n", temp.row, temp.col); } int main() { int n, m; int P; scanf("%d%d%d", &n, &m, &P); //申请内存 int** nums = (int**)malloc(sizeof(int*) * n); for (int i = 0; i < n; i++) { nums[i] = (int*)malloc(sizeof(int) * m); } //输入数据 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &nums[i][j]); StackInit(&STACK); StackInit(&MIN_STACK); POS entry = { 0,0 }; FindWay(nums, n, m, entry, P); //如果找路之后保存最短路径的栈为空，就说明青蛙不能走出迷宫 if(!StackEmpty(&MIN_STACK)) PrintWay(); else printf("Can not escape!\n"); //释放动态内存 for(int i = 0; i < n; i++) free(nums[i]); free(nums); StackDestory(&STACK); StackDestory(&MIN_STACK); return 0; }
