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
50
51
52
53
54
55
56
57
58
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
}
|