aboutsummaryrefslogtreecommitdiff
path: root/oob_path.c
blob: fb33dfa1a0386d14ed3a61b44d8a2afc9c5b23ec (plain)
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
}