迷宫问题——I
思路
创建二维数组，并实现输入
首先输入二维数组的行和列：
int n, m; scanf("%d%d", &n, &m);
然后动态开辟二维数组：
注：对动态开辟还不太了解的同学可以看看👉C语言——动态内存管理
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]);
实现找路（FindWay）
首先，为了方便记录，我们可以定义一个结构体来记录二维数组每一个位置的坐标
注：对结构体操作不太了解的小伙伴看这里👉传送门
typedef struct Position { int row; int col; }POS;
接着，我们应该确定找路的整体思路：
- 从上、下、左、右四个方向分别探路
- 探路之前，要对将要前进到区域进行有效性判断，如果符合条件再前进，否则选择下一个方向
- 如果，四个方向都无法前进，那么说明是个死路，就要进行回溯，由此，可以推出，需要用递归算法实现
- 由回溯的位置再次选择方向前进，为了避免走相同的路，我们应该在走过的每个点位做上标记，例如修改为除0，1的数据
判断位置有效性（Judge）：
bool Judge(int** nums, int n, int m, POS pos) { /* 如果数组越界 或者该点位的数据不是0 就说明该点位无效，不能前进 */ if (pos.col >= m || pos.col < 0 || pos.row >= n || pos.row < 0 || nums[pos.row][pos.col] != 0) { return false; } else return true; }
FindWay主体：
FindWay(int** nums, int n, int m, POS entry) { nums[entry.row][entry.col] = -1; //上 POS next = entry; next.row--; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next) } //下 next = entry; next.row++; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next) } //左 next = entry; next.col--; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next) } //右 next = entry; next.col++; if (Judge(nums, n, m, next)) { FindWay(nums, n, m, next) } }
这样写会造成一个问题：经过调试我们可以发现，这个函数并没有实现走到右下角（出口）便结束的功能，这个函数结束时，停留的位置会在出口处（因为可以走的的地方全部被标记为-1，当无路可走的时候就会回溯，最后就会回到出口），因此，我们可以将FindWay()函数的返回值设定为bood类型，当走到出口时就退出函数：
bool FindWay(int** nums, int n, int m, POS 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; } return false; }
保存正确的路径
很容易想到，我们可以用一个数组来保存我们每走过的下标位置。但是当我们进行回溯的时候又要不断对无效的路径进行删除，可见只是单纯的用一个数组是不方便实现的。
我们可以用栈的“先入后出”的特性来实现
注：对于栈的基本操作还不太熟悉的小伙伴可以看看👉栈的基本操作
- 每走到一个位置，就将这个位置入栈
- 如果走到的位置无法前进，就说明这个点位是思路，需要回溯，每回溯一个点位，就需要将这个点位删除（出栈）
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); } }
实现代码：
#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(); return 0; }
