leetcode 980. Unique Paths III

On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

Note:

1 <= grid.length * grid[0].length <= 20

思路：深搜，终止条件到达目标位置，以及可到达的位置全部走了一遍，算一条路径。

 1 class Solution {
 2     int dx[4] = {0, -1, 0, 1};
 3     int dy[4] = {1, 0, -1, 0};
 4 public:
 5     int uniquePathsIII(vector<vector<int>>& grid) {
 6         int m = grid.size();
 7         if (m == 0)
 8             return 0;
 9         int n = grid[0].size();
10         int todo = 0;
11         int start_x, start_y, end_x, end_y;
12         for (int i = 0; i < m; i++) {
13             for (int j = 0; j < n; j++) {
14                 if (grid[i][j] != -1) { //记录要走的总的位置数
15                     todo++;
16                     if (grid[i][j] == 1) { //记录起始位置
17                         start_x = i;
18                         start_y = j;
19                     } else if (grid[i][j] == 2) { //记录终点
20                         end_x = i;
21                         end_y = j;
22                     }
23                 }
24             }
25         }
26         int ans = 0;
27         dfs(grid, start_x, start_y, end_x, end_y, todo, ans, m, n);
28         return ans;
29     }
30     void dfs(vector<vector<int> > &grid, int sx, int sy, const int ex, const int ey, int todo, int &ans, int row, int col) {
31         todo--;
32         if (todo < 0)
33             return ;
34         if (sx == ex && sy == ey) {
35             if (todo == 0) ans++;
36             return;
37         }
38         //上下左右四个方向
39         for (int k = 0; k < 4; k++) {
40             int new_x = sx + dx[k];
41             int new_y = sy + dy[k];
42             if (new_x >= 0 && new_x < row && new_y >= 0 && new_y < col) {
43                 if (grid[new_x][new_y] == 0 || grid[new_x][new_y] == 2) {
44                     grid[new_x][new_y] = -1;
45                     dfs(grid, new_x, new_y, ex, ey, todo, ans, row, col);
46                     grid[new_x][new_y] = 0;
47                 }
48             }
49         }
50     }
51 };