c - 如何在C中使用递归找到穿过迷宫的路径

Question

我必须用C语言构建一个递归函数来检查矩阵中是否存在路径(NxN大小，内部只有0和1输入)，其中我从左上角开始，到右下角结束。我只允许通过零并向上、向下、向右、向左行走。

我从左上角的 (0,0) 开始我的路径

我尝试过这个，但效果不佳。

int x = 0, y = 0;
int isPathExist(char board[][N], int row, int col)
{

    board[x][y] = 1;

    if (x == N - 1 && y == N - 1) {
        return 1;
    }

    if (x + 1 < N && board[x + 1][y] == 0) {
        if (isPathExist(board, x + 1, y)) {
            return 1;
        }
    }

    if (x - 1 >= 0 && board[x - 1][y] == 0) {
        if (isPathExist(board, x - 1, y)) {
            return 1;
        }
    }

    if (y + 1 < N && board[x][y + 1] == 0) {
        if (isPathExist(board, x, y + 1)) {
            return 1;
        }
    }

    if (y - 1 >= 0 && board[x][y - 1] == 0) {
        if (isPathExist(board, x, y - 1)) {
            return 1;
        }
    }

    board[x][y] = 0;

    return 0;
}

Answer 1

基本(最简单)的方法是“将左(或右手)手放在墙上”。这意味着执行以下步骤的循环:

• 根据您上次移动时所面对的方向，使用顺时针顺序确定移动方向(例如，如果您向北移动，则检查是否可以向西，然后向北，然后向东，然后向南)。

• 朝您确定可以移动的第一个方向移动

• 检查您以前是否去过该位置，如果去过则丢弃您所走的部分路径。例如，如果您向北移动进入死胡同，并且必须向南移动，请修改到目前为止所走的路径，以便看起来您一开始就没有去过北方。最简单的方法是对步数进行编号 - 每次移动到以前没有去过的位置时，在该位置存储“到目前为止我移动的次数”值，以便稍后可以使用该值更容易放弃之前采取的路径的那部分。先前采取的路径可以是“位置或丢弃”值的数组，以“每次移动的次数”为索引。

• 检查是否已到达导出，以及是否还没有循环回到起点。

在实现此循环(无递归)并检查以确保其正常工作后；你只需要通过某种方式将不必要的递归塞进代码中，让代码变得更糟糕(更慢，更难以阅读，并且更有可能因耗尽堆栈空间而崩溃)。最简单的方法是修改循环，以便最后一件事(“检查是否已到达导出，以及是否还没有循环回到开始处”)变成函数调用(“检查是否已到达”)已到达导出，如果您还没有给自己打电话”)。

警告: 你的问题说“找到一条路径”，这个算法会做到这一点。然而，如果有多个可能的路径，该算法可能找不到最短路径(或最长路径)。出于这个原因(假设它是大学作业或其他什么)，我建议检查要求以确保“任何路径”都是可接受的。