Finding paths through matrix 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 &lt;iostream&gt;

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

bool pathCount(int (&amp;matrix)[ROW][COL], int M, int N, int m, int n, int &amp;paths)
{
  std::cout &lt;&lt; "@ (" &lt;&lt; m &lt;&lt; ", " &lt;&lt; n &lt;&lt; ")" &lt;&lt; std::endl;
  if (m == M - 1 &amp;&amp; n == N - 1 &amp;&amp; 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 (&amp;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?
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 &lt;iostream&gt;
#include &lt;chrono&gt;

#define ROW 15
#define COL 15

void pathCount(int (&amp;matrix)[ROW][COL], int M, int N, int m, int n, int &amp;paths) {
    if (m == M - 1 &amp;&amp; n == N - 1 &amp;&amp; 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 (&amp;matrix)[ROW][COL], int M, int N) {
    int paths = 0;
    pathCount(matrix, M, N, 0, 0, paths);
    return paths;
}

int pathCountV2(int (&amp;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 &lt; 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 &lt; 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 &lt; ROW; ++y) 
    {
        for (int x = 1; x &lt; 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&lt;
           std::chrono::milliseconds&gt;(
           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 &lt; ROW; ++y) {
        for (size_t x = 0; x &lt; 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 &lt;&lt; "Paths: " &lt;&lt; path_count &lt;&lt; " in " &lt;&lt; tb - ta &lt;&lt; " ms."
              &lt;&lt; std::endl;

    path_count = 0;

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

    std::cout &lt;&lt; "Paths: " &lt;&lt; path_count2 &lt;&lt; " in " &lt;&lt; tb - ta &lt;&lt; " ms."
              &lt;&lt; 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.