-2

I was asked to solve a problem in advanced programming course that was "Say if there is any horizonal-vertical way of '0's in a 0 & 1 matrix from index[0][0] to index[n][n]?" and guided that can be solve by recursive function. In next session, the instructor solved it and I didn't understand how it works. I put the code below.

#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;
}

Can someone explain it to my like I'm "eli5"?

Reza
  • 1
  • `int c[n][N];`: This is invalid C++. See [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/q/1887097) – prapin Feb 26 '22 at 19:10

1 Answers1

0

The algorithm tries to find a path from (0, 0) => (n-1, n-1). For the two dimension matrix (c), 0 indicates ok to walk, 1 means already visited or wall, 2 means destination.

path(c, n, 0, 0) means to the start point is (0, 0).

if (i < 0 || j < 0 || i >= n || j >= n || d[i][j] == 1) means if the index is out of boundary or wall or visited, then it indicates this is not a valid path.

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); means to walk to right, left, down, or up. if any direction works, it indicates there is a valid path.

Boris Hu
  • 202
  • 1
  • 6