-
Notifications
You must be signed in to change notification settings - Fork 820
/
OutOfBoundaryPaths.java
49 lines (43 loc) · 1.67 KB
/
OutOfBoundaryPaths.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/* (C) 2024 YourCompanyName */
package dynamic_programming;
/**
* Created by gouthamvidyapradhan on 15/05/2019 There is an m by n grid with a ball. Given the start
* coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary
* in four directions (up, down, left, right). However, you can at most move N times. Find out the
* number of paths to move the ball out of grid boundary. The answer may be very large, return it
* after mod 10 ^ 9 + 7.
*
* <p>Solution: O(m x n x N x 4) Move in all possible directions from the starting position (i, j)
* and keep track of distance traversed and ensure the distance traversed does not exceed N. Keep
* the count of number of possibilities to go out of the boundary for each cell reached. Return the
* sum in cell (a, b)
*/
public class OutOfBoundaryPaths {
final int[] R = {1, -1, 0, 0};
final int[] C = {0, 0, 1, -1};
int[][][] DP;
int mod = 1000000007;
public static void main(String[] args) {
System.out.println(new OutOfBoundaryPaths().findPaths(2, 2, 2, 0, 0));
}
public int findPaths(int m, int n, int N, int a, int b) {
if (N == 0) return 0;
DP = new int[m][n][N + 1];
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int p = 0; p < 4; p++) {
int newR = i + R[p];
int newC = j + C[p];
if (newR < 0 || newC < 0 || newR >= m || newC >= n) {
DP[i][j][k] = ((DP[i][j][k] + 1) % mod);
} else {
DP[i][j][k] = (((DP[i][j][k] + DP[newR][newC][k - 1])) % mod);
}
}
}
}
}
return DP[a][b][N];
}
}