[LeetCode] 980. Unique Paths III
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 }
LeetCode 题目总结