DEV Community

Wenqi Jiang
Wenqi Jiang

Posted on

Labyrinthian Possibilities

#java #algorithms #programming #100daysofcode

Description

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? Mod the result by 10 ** 9 + 7.

You can only move right and down. 0 represents an empty space while 1 represents a wall you cannot walk through. The top left corner and bottom right corner will always be 0.

Constraints:

  • 1 ≤ n, m ≤ 250 where n and m are the number of rows and columns in matrix.

Example 1

Input 

matrix = [
    [0, 0, 1],
    [0, 0, 1],
    [1, 0, 0]
]
Enter fullscreen mode Exit fullscreen mode

Output 

2
Enter fullscreen mode Exit fullscreen mode

Explanation 

There are two ways to get to the bottom right:

Right, down, down, right
Down, right, down, right
Enter fullscreen mode Exit fullscreen mode

Example 2

Input 

matrix = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
]
Enter fullscreen mode Exit fullscreen mode

Output 

6
Enter fullscreen mode Exit fullscreen mode

Explanation 

There are 6 ways here:

Right, right, down, down
Down, down, right, right
Right, down, right, down
Down, right, down, right
Right, down, down, right
Down, right, right, down
Enter fullscreen mode Exit fullscreen mode

Example 3

Input 

matrix = [
    [0, 0, 0],
    [1, 1, 1],
    [0, 0, 0]
]
Enter fullscreen mode Exit fullscreen mode

Output 

0
Enter fullscreen mode Exit fullscreen mode

Explanation 

There is a wall in the middle preventing us from getting to the bottom right.
Enter fullscreen mode Exit fullscreen mode

Example 4

Input 

matrix = [
    [0, 0, 0, 0],
    [1, 1, 1, 0],
    [0, 0, 0, 0]
]
Enter fullscreen mode Exit fullscreen mode

Output 

1
Enter fullscreen mode Exit fullscreen mode

Example 5

Input 

matrix = [
    [0, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0]
]
Enter fullscreen mode Exit fullscreen mode

Output 

3
Enter fullscreen mode Exit fullscreen mode

Intuition

DP[i-1][j-1] means how many different ways to[i][j]

if [i][j] is 1, no way

else dp[i][j] = dp[i-1][j] + dp[i][j-1]

Implementation 

class Solution {
    private final int MOD = (int) (Math.pow(10, 9) + 7);

    public int solve(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = matrix[0][0] == 0 ? 1 : 0;
        if (dp[0][0] == 0) {
            return 0;
        }
        // first row
        for (int i = 1; i < cols; i++) {
            if (matrix[0][i] == 1) {
                dp[0][i] = 0;
            } else {
                dp[0][i] = dp[0][i - 1];
            }
        }

        // first column
        for (int i = 1; i < rows; i++) {
            if (matrix[i][0] == 1) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }

        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                if (matrix[row][col] == 1) {
                    dp[row][col] = 0;
                } else {
                    dp[row][col] = (dp[row - 1][col] + dp[row][col - 1]) % MOD;
                }
            }
        }
        return dp[rows - 1][cols - 1];
    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity

  • Time: O(n)
  • Space: O(n)

Top comments (0)

Read next

fazicodes profile image

20 Free Api For Your Next Project

fazicodes -

victorpreston profile image

Most In-Demand Tech Careers & Skills for 2024.

Victor Preston -

jukilo_lokiju profile image

3 resources from Beginner to PRO to learn Ruby on Rails

The Monkey Dev -

spiff profile image

Bitcoin Sentiment Analysis using Python and X (Formerly Twitter)

Ebikara Dandeson Spiff -