aboutsummaryrefslogtreecommitdiff
path: root/oob_path.c
diff options
context:
space:
mode:
Diffstat (limited to 'oob_path.c')
-rw-r--r--oob_path.c59
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
+}