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
- 1 ≤ r, c ≤ 1000
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
- A cell can only be entered from above or from the left.
- 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