[LeetCode] 980. Unique Paths III

CNoodle / 2023-08-04 / 原文

You are given an m x n integer array grid where grid[i][j] could be:

1 representing the starting square. There is exactly one starting square.
2 representing the ending square. There is exactly one ending square.
0 representing empty squares we can walk over.
-1 representing 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: grid = [[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: grid = [[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: grid = [[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.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 20
1 <= m * n <= 20
-1 <= grid[i][j] <= 2
There is exactly one starting cell and one ending cell.

不同路径 III。

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是 DFS + 回溯。这道题的题设还是一个在矩阵内做遍历，最终找到一个目标位置。题目告诉你每一个无障碍方格（0）都要通过一次，但是一条路径中不能重复通过同一个方格。这个条件也就意味着我们从起始方格到结束方格的步数是有限制的，也就是矩阵中 0 的个数，这里我记为 steps。所以除了常规的 dfs 遍历，我们需要在 dfs 函数中额外带上参数 steps，每经过一个可以走的点就减去一步，走过去的空格可以用障碍物（-1）来标记以免重复走。找到结束方格的时候我们需要判断 steps == 0，如果不为 0，说明还有空方格（0）未遍历到，则不是一个合法的解。

时间O(4^(r*c)) - 在矩阵的每个位置都可以往上下左右四个方向走，其实是一个四叉树

空间O(r*c) - 递归栈的深度

Java实现

 1 class Solution {
 2     int m;
 3     int n;
 4 
 5     public int uniquePathsIII(int[][] grid) {
 6         int startX = 0;
 7         int startY = 0;
 8         int steps = 1;
 9         m = grid.length;
10         n = grid[0].length;
11         for (int i = 0; i < m; i++) {
12             for (int j = 0; j < n; j++) {
13                 // 找到起点坐标
14                 if (grid[i][j] == 1) {
15                     startX = i;
16                     startY = j;
17                     continue;
18                 }
19                 // 计算0的个数 - 计算需要多少步遍历完矩阵内所有的空格
20                 if (grid[i][j] == 0) {
21                     steps++;
22                 }
23             }
24         }
25         return dfs(startX, startY, steps, grid);    
26     }
27 
28     private int dfs(int i, int j, int steps, int[][] grid) {
29         // 越界
30         if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == -1) {
31             return 0;
32         }
33 
34         // 到达终点，如果步数不为0则不是一个合法的解
35         if (grid[i][j] == 2) {
36             return steps == 0 ? 1 : 0;
37         }
38         // 用障碍物标记走过的空格
39         grid[i][j] = -1;
40         int res = 0;
41         res += dfs(i - 1, j, steps - 1, grid);
42         res += dfs(i + 1, j, steps - 1, grid);
43         res += dfs(i, j - 1, steps - 1, grid);
44         res += dfs(i, j + 1, steps - 1, grid);
45         // 回溯
46         grid[i][j] = 0;
47         return res;
48     }
49 }