题解 | #迷宫问题 C语言#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 搜寻函数，用于对矩阵进行处理
void search(int** arr, int x, int y, int m, int n, char*** stack, int* top,
            char*** resstack, int* restop) {
    // 对当前位置的元素，先假设它能走得通，对于走得通的元素，
    // 将其值改为1，标记其已经走过，防止下次寻找时再次走到这个位置
    arr[x][y] = 1;
    // 将当前的字符串先入栈，后面如果发现当前位置不合适的话，再弹栈
    sprintf((*stack)[(*top)++], "(%d,%d)", x, y);
    if (x == m - 1 && y == n - 1) { // 当前位置是最后一个位置
        // 将当前的stack复制到保存结果的栈resstack中
        // 在后续递归返回时，stack会被改变
        for (*restop = 0; (*restop) < (*top); (*restop)++) {
            strcpy((*resstack)[*restop], (*stack)[*restop]);
        }
        return;
    }
    // 按照上->右->下->左的顺序依次寻找可以走的路径
    // 是多个if而不是if else，因为当发现位置不合适需要回溯时，else部分将不会再执行，
    // 即回溯时将不再查看当前位置的其他可能位置，即上下左右四个方向将只会寻找一个方向，
    // 只有用4个if才会在回溯时将四个方向全都找一遍
    if (x - 1 >= 0 && arr[x - 1][y] == 0) { //上
        search(arr, x - 1, y, m, n, stack, top, resstack, restop);
    }
    if (y + 1 < n && arr[x][y + 1] == 0) { //右
        search(arr, x, y + 1, m, n, stack, top, resstack, restop);
    }
    if (x + 1 < m && arr[x + 1][y] == 0) { //下
        search(arr, x + 1, y, m, n, stack, top, resstack, restop);
    }
    if (y - 1 >= 0 && arr[x][y - 1] == 0) { //左
        search(arr, x, y - 1, m, n, stack, top, resstack, restop);
    }
    // 如果上下左右四个方向全都不可以，则需要进行回溯（利用递归来回溯），stac要弹栈
    --(*top);
}

int main(void) {
    // 读取输入
    // 读取行列
    int m, n; // m行，n列
    scanf("%d %d", &m, &n);
    // 定义二维数组
    int** arr = (int**)malloc(sizeof(int*) * m);
    for (int i = 0; i < m; i++)
        arr[i] = (int*)malloc(sizeof(int) * n);
    // 读取二维数组
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    // 定义两个栈，用于对数组进行处理
    // 定义第一个栈，用于寻找
    char** stack = (char**)malloc(sizeof(char*) * 40);
    for (int i = 0; i < 40; i++) {
        stack[i] = (char*)malloc(sizeof(char) * 10);
    }
    int top = 0;
    // 定义第二个栈，用于返回结果
    char** res = (char**)malloc(sizeof(char*) * 40);
    for (int i = 0; i < 40; i++) {
        res[i] = (char*)malloc(sizeof(char) * 10);
    }
    int restop = 0;
    // 调用搜寻函数进行处理
    search(arr, 0, 0, m, n, &stack, &top, &res, &restop);
    // 打印结果，结果保存在用于返回结果的第二个栈中
    for (int i = 0; i < restop; i++)
        puts(res[i]);
    return 0;
}