Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Unique Paths with Obstacles

Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Bloomberg

A robot starts at the top-left cell and moves only right or down to the bottom-right cell. Cells with 1 are obstacles. Print the number of different paths modulo 1,000,000,007.

Input

First line: r c. Next r lines: c values (0 = free, 1 = obstacle).

Output

The number of paths modulo 10^9 + 7.

Constraints

ways[i][j] = 0 on an obstacle, otherwise ways[i−1][j] + ways[i][j−1]. One row of memory is enough.

Example 1

Input

3 3
0 0 0
0 1 0
0 0 0

Output

2

Example 2

Input

2 2
0 1
0 0

Output

1

Hints

  1. A cell can only be entered from above or from the left.
  2. ways[i][j] = 0 for an obstacle, otherwise ways[i−1][j] + ways[i][j−1] (mod 10^9 + 7). The start has 1 way unless it is blocked.

Approach

Keep one row w of path counts. Going left to right through each row, w[j] still holds the count from the row above, and w[j−1] already holds the current row's left neighbour — so w[j] = (w[j] + w[j−1]) % MOD, or 0 on an obstacle. Initialise w[0] = 1; an obstacle at the start immediately zeroes it.

Complexity: O(r · c) time · O(c) space

Solution

C++ solution

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

int main() {
    int R, C;
    cin >> R >> C;
    const long long MOD = 1000000007LL;
    vector<long long> w(C, 0);
    w[0] = 1;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            int x;
            cin >> x;
            if (x) w[j] = 0;
            else if (j > 0) w[j] = (w[j] + w[j - 1]) % MOD;
        }
    cout << w[C - 1] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
R, C = data[0], data[1]
g = data[2:]
MOD = 10**9 + 7
w = [0] * C
w[0] = 1
for i in range(R):
    for j in range(C):
        if g[i * C + j]:
            w[j] = 0
        elif j:
            w[j] = (w[j] + w[j - 1]) % MOD
print(w[C - 1])

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int R = (int) in.nval;
        in.nextToken();
        int C = (int) in.nval;
        long MOD = 1000000007L;
        long[] w = new long[C];
        w[0] = 1;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++) {
                in.nextToken();
                if ((int) in.nval == 1) w[j] = 0;
                else if (j > 0) w[j] = (w[j] + w[j - 1]) % MOD;
            }
        System.out.println(w[C - 1]);
    }
}

Solve Unique Paths with Obstacles online · All practice problems