diff options
Diffstat (limited to 'oob_path.c')
-rw-r--r-- | oob_path.c | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/oob_path.c b/oob_path.c new file mode 100644 index 0000000..fb33dfa --- /dev/null +++ b/oob_path.c @@ -0,0 +1,59 @@ +// 576. Out of Boundary Paths +#include "leetcode.h" + +/* + * there is an 'm * n' grid with a ball. the ball is initially at the position + * '[start_row, start_column]'. you are allowed to move the ball to one of the + * four adjacent cells in the grid (possible out of the grid crossing the grid + * boundary). you can apply at most 'max_move' moves to the ball. given the give + * integers, 'm', 'n', 'max_move', 'start_row', 'and start_column', return the + * number of paths to move the ball out of the grid boundary. since the answer + * can be very large, return it modulo 10^9+7 + */ + +void dfs(int m, int n, int max, int x, int y, int k, long *cnt, long ***cache) { + if (x >= m || x < 0 || y >= n || y < 0) { + (*cnt)++; + (*cnt) %= 1000000007; + return; + } + if (cache[x][y][k] != -1) { + (*cnt) = cache[x][y][k]; + return; + } + if (k == max) + return; + long a = 0, b = 0, c = 0, d = 0; + dfs(m, n, max, x + 1, y, k + 1, &a, cache); + dfs(m, n, max, x - 1, y, k + 1, &b, cache); + dfs(m, n, max, x, y + 1, k + 1, &c, cache); + dfs(m, n, max, x, y - 1, k + 1, &d, cache); + cache[x][y][k] = a + b + c + d; + cache[x][y][k] %= 1000000007; + (*cnt) = cache[x][y][k]; +} + +int findPaths(int m, int n, int max_move, int start_row, int start_column) { + if (!max_move) + return 0; + long ***cache = (long ***)malloc(m * sizeof(long **)); + for (int i = 0; i < m; i++) { + cache[i] = (long **)malloc(n * sizeof(long *)); + for (int j = 0; j < n; j++) { + cache[i][j] = (long *)malloc((max_move + 1) * sizeof(long)); + memset(cache[i][j], -1, (max_move + 1) * sizeof(long)); + } + } + long cnt = 0; + dfs(m, n, max_move, start_row, start_column, 0, &cnt, cache); + for (int i = 0; i < m; i++) + for (int j = 0; j < n; j++) + free(cache[i][j]); + free(cache); + return cnt; +} + +int main() { + printf("%d\n", findPaths(2, 2, 2, 0, 0)); // expect: 6 + printf("%d\n", findPaths(1, 3, 3, 0, 1)); // expect: 12 +} |