友情支持
如果您觉得这个笔记对您有所帮助，看在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
思路分析
回溯。
找到起点，然后向四面八方扩散，遇到空格就前进，否则就回溯，到达终点则计数，否则计数为 0。
-
一刷
-
二刷
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;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-21 16:39:19
*/
public int uniquePathsIII(int[][] grid) {
int[] start = new int[2];
int[] end = new int[2];
int step = 0;
for (int c = 0; c < grid.length; c++) {
for (int r = 0; r < grid[c].length; r++) {
if (grid[c][r] == 1) {
start[0] = c;
start[1] = r;
} else if (grid[c][r] == 2) {
end[0] = c;
end[1] = r;
} else if (grid[c][r] == 0) {
step++;
}
}
}
return backtrack(grid, start, end, step + 1);
}
private int backtrack(int[][] grid, int[] start, int[] end, int step) {
int column = start[0];
int row = start[1];
if (step == 0 && column == end[0] && row == end[1]) {
return 1;
}
if (column < 0 || column >= grid.length
|| row < 0 || row >= grid[column].length
|| step < 0
|| (grid[column][row] != 1 && grid[column][row] != 0)) {
return 0;
}
int origin = grid[column][row];
int nextStep = step - 1;
grid[column][row] = Integer.MAX_VALUE;
int result = 0;
// 上
result += backtrack(grid, new int[]{column - 1, row}, end, nextStep);
// 下
result += backtrack(grid, new int[]{column + 1, row}, end, nextStep);
// 左
result += backtrack(grid, new int[]{column, row - 1}, end, nextStep);
// 右
result += backtrack(grid, new int[]{column, row + 1}, end, nextStep);
grid[column][row] = origin;
return result;
}