-2

我被要求解决高级编程课程中的一个问题，即“假设从 index[0][0] 到 index[n][n] 的 0 和 1 矩阵中是否存在任何水平 - 垂直方式的 '0？” 并引导可通过递归函数求解。在下一节课中，导师解决了它，我不明白它是如何工作的。我把代码放在下面。

#include <iostream>
#include <vector>
using namespace std;

#define N 10

bool path(int d[][N], int n, int i, int j)
{
    if (i < 0 || j < 0 || i >= n || j >= n || d[i][j] == 1)
    {
        return false;
    }
    if (d[i][j] == 0)
    {
        d[i][j] = 1;
    }

    if (d[i][j] == 2)
    {
        return true;
    }

    return path(d, n, i, j + 1) || path(d, n, i, j - 1) || path(d, n, i + 1, j) || path(d, n, i - 1, j);
}

int main()
{
    int n;
    cin >> n;
    int c[n][N];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> c[i][j];
        }
    }
    c[n - 1][n - 1] = 2;
    if (path(c, n, 0, 0))
    {
        cout << "YES";
    }
    else
    {
        cout << "NO";
    }

    return 0;
}

有人可以像我“eli5”一样向我解释吗？

4

1 回答 1

0

该算法试图从 (0, 0) => (n-1, n-1) 中找到一条路径。对于二维矩阵 (c)，0 表示可以步行，1 表示已经访问过或墙壁，2 表示目的地。

path(c, n, 0, 0)表示起点为 (0, 0)。

if (i < 0 || j < 0 || i >= n || j >= n || d[i][j] == 1)表示如果索引超出边界或墙或已访问，则表明这不是有效路径。

return path(d, n, i, j + 1) || path(d, n, i, j - 1) || path(d, n, i + 1, j) || path(d, n, i - 1, j);表示向右、向左、向下或向上行走。如果任何方向有效，则表明存在有效路径。

于 2022-02-26T20:49:56.670 回答