1
class Solution {
2
  int walk = 0;
3

4
  public int uniquePathsIII(int[][] grid) {
5
    int m = grid.length;
6
    int n = grid[0].length;
7
    for (int i = 0; i < m; i++) {
8
      for (int j = 0; j < n; j++) {
9
        if (grid[i][j] == 0) {
10
          walk++;
11
        }
12
      }
13
    }
14
    for (int i = 0; i < m; i++) {
15
      for (int j = 0; j < n; j++) {
16
        if (grid[i][j] == 1) {
17
          return ways(grid, i, j, m, n, 0);
18
        }
19
      }
20
    }
21
    return 0;
22
  }
23

24
  public int ways(int[][] grid, int cr, int cc, int m, int n, int count) {
25
    if (cr < 0 || cr == m || cc < 0 || cc == n || grid[cr][cc] == -1) {
26
      return 0;
27
    }
28
    if (grid[cr][cc] == 2) {
29
      if (count - 1 == walk) return 1;
30
      return 0;
31
    }
32
    grid[cr][cc] = -1;
33
    int ans = 0;
34
    int[] r = {0, 1, 0, -1};
35
    int[] c = {1, 0, -1, 0};
36
    for (int i = 0; i < 4; i++) {
37
      ans += ways(grid, cr + r[i], cc + c[i], m, n, count + 1);
38
    }
39
    grid[cr][cc] = 0;
40
    return ans;
41
  }
42
}