Number of ways to move from top left corner to bottom right corner

You are given an N by M matrix of 0s and 1s. Starting from the top left corner, how many ways are there to reach the bottom right corner?

You can only move right and down. 0 represents an empty space while 1 represents a wall you cannot walk through.

For example, given the following matrix:

[[0, 0, 1],
 [0, 0, 1],
 [1, 0, 0]]

Return two, as there are only two ways to get to the bottom right:

• Right, down, down, right
• Down, right, down, right

The top left corner and bottom right corner will always be 0

Example:

Input:  matrix = {{0, 0, 1}, {0, 0, 1}, {1, 0, 0}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int numberOfWays(vector<vector<int>> &matrix)
{
    int n = matrix.size();
    if (n == 0)
        return 0;
    int m = matrix[0].size();
    int dp[n][m];
    for (int i = 0; i < n; i++)
    {
        if (matrix[i][0] == 1)
        {
            while (i < n)
            {
                dp[i][0] = 0;
                i++;
            }
        }
        else
            dp[i][0] = 1;
    }
    for (int i = 0; i < m; i++)
    {
        if (matrix[0][i] == 1)
        {
            while (i < m)
            {
                dp[0][i] = 0;
                i++;
            }
        }
        else
            dp[0][i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            if (matrix[i][j] == 1)
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[n - 1][m - 1];
}
int main()
{

    vector<vector<int>> matrix = {{0, 0, 1},
                                  {0, 0, 1},
                                  {1, 0, 0}};

    cout << numberOfWays(matrix) << "\n";

    return 0;
}