Finding paths through matrix
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.