1
class Solution {
2
 public:
3
  int dfs(vector<vector<int>> &grid, int x, int y, int zero) {
4
    // Base Condition
5
    if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == -1) {
6
      return 0;
7
    }
8
    if (grid[x][y] == 2) {
9
      return zero == -1 ? 1 : 0; // Why zero = -1, because in above example we
10
                                 // have 9 zero's. So, when we reach the final
11
                                 // cell we are covering one cell extra that
12
                                 // means if all zero all covered then on
13
                                 // reaching final it will make zero count = -1
14
      // If that's the case we find the path and return '1' otherwise return
15
      // '0';
16
    }
17
    grid[x][y] = -1; // mark the visited cells as -1;
18
    zero--;          // and reduce the zero by 1
19

20
    int totalPaths = dfs(grid, x + 1, y,
21
                         zero) + // calculating all the paths available in 4 directions
22
                     dfs(grid, x - 1, y, zero) +
23
                     dfs(grid, x, y + 1, zero) + dfs(grid, x, y - 1, zero);
24

25
    // Let's say if we are not able to count all the paths. Now we use
26
    // Backtracking over here
27
    grid[x][y] = 0;
28
    zero++;
29

30
    return totalPaths; // if we get all the paths, simply return it.
31
  }
32

33
  int uniquePathsIII(vector<vector<int>> &grid) {
34
    int start_x, start_y = 0, cntzero = 0;
35

36
    for (int i = 0; i < grid.size(); i++) {
37
      for (int j = 0; j < grid[0].size(); j++) {
38
        if (grid[i][j] == 0)
39
          cntzero++;
40
        else if (grid[i][j] == 1) {
41
          start_x = i;
42
          start_y = j;
43
        }
44
      }
45
    }
46
    return dfs(grid, start_x, start_y, cntzero);
47
  }
48
};