Finding paths through matrix

Question

Given the problem:

You are given a 2-Dimensional array with M rows and N columns. You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right or downwards. The array is filled with 1's and 0's. A 1 indicates that you can move through that cell, a 0 indicates that you cannot move through the cell. Return the number of paths from the top-left cell to the bottom-right cell (i.e. (0,0) to (M-1,N-1)).

And my implementation:

#include <iostream>

#define ROW M // Fill this in
#define COL N // Fill this in

bool pathCount(int (&matrix)[ROW][COL], int M, int N, int m, int n, int &paths)
{
  std::cout << "@ (" << m << ", " << n << ")" << std::endl;
  if (m == M - 1 && n == N - 1 && matrix[m][n]) {
      ++paths;
      return false;
  } else if (m == M || n == N || !matrix[m][n]) {
      return false;
  }

  while (pathCount(matrix, N, M, m, n + 1, paths));
  while (pathCount(matrix, N, M, m + 1, n, paths));

  return false;
}

int pathCount(int (&matrix)[ROW][COL], int M, int N)
{
  int paths = 0;
  pathCount(matrix, M, N, 0, 0, paths);
  return paths;
}

Are there any improvements or potential bugs in the implementation? I ran it through a few tests. In terms of performance I am seeing this as having worst-case complexity of \$O(n + m)\$ which is the complexity of depth first search. Is that correct?

Answer 1

The complexity of your approach is actually $$\mathcal{O}\Big((N + M)\frac{(N + M - 2)!}{(N-1)!(M-1)!}\Big),$$ but using a dynamic programming algorithm you can drop it to \$\Theta(MN)\$:

#include <iostream>
#include <chrono>

#define ROW 15
#define COL 15

void pathCount(int (&matrix)[ROW][COL], int M, int N, int m, int n, int &paths) {
    if (m == M - 1 && n == N - 1 && matrix[m][n]) {
        ++paths;
        return;
    }

    if (m == M || n == N || !matrix[m][n]) {
        return;
    }

    pathCount(matrix, N, M, m, n + 1, paths);
    pathCount(matrix, N, M, m + 1, n, paths);
}

int pathCount(int (&matrix)[ROW][COL], int M, int N) {
    int paths = 0;
    pathCount(matrix, M, N, 0, 0, paths);
    return paths;
}

int pathCountV2(int (&matrix)[ROW][COL], int M, int N) {
    if (!matrix[0][0]) 
    {
        // The starting cell is not traversable.
        return 0;
    }

    int aux[ROW][COL];

    bool zero_encountered = false;

    for (int y = 0; y < ROW; ++y) 
    {
        if (zero_encountered) 
        {
            aux[y][0] = 0;
        } 
        else if (!matrix[y][0])
        {
            aux[y][0] = 0;
            zero_encountered = true;
        } 
        else 
        {
            aux[y][0] = 1;
        }
    }

    zero_encountered = false;

    for (int x = 1; x < COL; ++x) 
    {
        if (zero_encountered) 
        {
            aux[0][x] = 0;
        } 
        else if (!matrix[0][x])
        {
            aux[0][x] = 0;
            zero_encountered = true;
        }
        else 
        {
            aux[0][x] = 1;
        }
    }

    for (int y = 1; y < ROW; ++y) 
    {
        for (int x = 1; x < COL; ++x) 
        {
            aux[y][x] = matrix[y][x] ? aux[y - 1][x] + aux[y][x - 1] : 0;
        }
    }

    return aux[M - 1][N - 1];
}

static long long get_milliseconds() {
    return std::chrono::duration_cast<
           std::chrono::milliseconds>(
           std::chrono::system_clock::now().time_since_epoch()).count();
}

int main(int argc, char** argv) {
    int matrix[ROW][COL];

    for (size_t y = 0; y < ROW; ++y) {
        for (size_t x = 0; x < COL; ++x) {
            matrix[y][x] = 1;
        }
    }

    matrix[ROW / 2][COL / 2] = 0;
    matrix[2][3] = 0;

    long long ta = get_milliseconds();
    int path_count = pathCount(matrix, ROW, COL);
    long long tb = get_milliseconds();

    std::cout << "Paths: " << path_count << " in " << tb - ta << " ms."
              << std::endl;

    path_count = 0;

    ta = get_milliseconds();
    int path_count2 = pathCountV2(matrix, ROW, COL);
    tb = get_milliseconds();

    std::cout << "Paths: " << path_count2 << " in " << tb - ta << " ms."
              << std::endl;

    return 0;
}

The space complexity of the above algorithm is also \$\Theta(MN)\$, but it can be easily improved to \$\Theta(\min\{M, N\})\$ by processing one column or row at a time.

Answer 2

pathcount() always returns false. Why? You can just have the return type be void, and then all the early-exits are just return;.

You're using an inefficient algorithm. There are many overlapping subproblems that are being calculated more than once. You ought to save that work somewhere so that you don't have to redo the calculations. Doing it that way, the best complexity is really \$O(m*n)\$.