友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
980. 不同路径 III
在二维网格 grid 上，有 4 种类型的方格：
-
1表示起始方格。且只有一个起始方格。 -
2表示结束方格，且只有一个结束方格。 -
0表示我们可以走过的空方格。 -
-1表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]] 输出：2 解释：我们有以下两条路径： 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)
示例 2：
输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]] 输出：4 解释：我们有以下四条路径： 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)
示例 3：
输入：[[0,1],[2,0]] 输出：0 解释： 没有一条路能完全穿过每一个空的方格一次。 请注意，起始和结束方格可以位于网格中的任意位置。
提示：
-
1 <= grid.length * grid[0].length <= 20
思路分析
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-13 20:29:14
*/
int result = 0;
int[][] options = new int[][]{
{-1, 0},// 上
{1, 0}, // 下
{0, 1}, // 右
{0, -1}, // 左
};
public int uniquePathsIII(int[][] grid) {
int row = grid.length;
int column = grid[0].length;
int sr = -1, sc = -1;
int path = 0;
for (int r = 0; r < row; r++) {
for (int c = 0; c < column; c++) {
if (grid[r][c] == 0) {
path++;
continue;
}
if (grid[r][c] == 1) {
sr = r;
sc = c;
path++;
}
}
}
backtrack(grid, sr, sc, path);
return result;
}
private void backtrack(int[][] grid, int sr, int sc, int path) {
// 如果越界，则排除
if (sr < 0 || grid.length <= sr || sc < 0 || grid[sr].length <= sc || path < 0) {
return;
}
if (grid[sr][sc] == Integer.MIN_VALUE || grid[sr][sc] == -1) {
return;
}
// 走到终点并且通过所有节点，则找到一个满足要求的结果
if (grid[sr][sc] == 2) {
if (path == 0) {
result++;
}
return;
}
int origin = grid[sr][sc];
grid[sr][sc] = Integer.MIN_VALUE;
for (int[] option : options) {
int r = sr + option[0];
int c = sc + option[1];
backtrack(grid, r, c, path - 1);
}
grid[sr][sc] = origin;
}