有没有从 arr[0][0] 到 arr[n][n] 的“0”的方法？ （不允许歪斜）

Question

我被要求解决高级编程课程中的一个问题，即“假设从索引 [0] [0] 到索引 [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”一样向我解释一下吗？

Answer 1

该算法尝试从 (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) 表示如果索引超出边界或墙壁或已访问，则表明这不是有效路径。

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