05 August 2008
类似题目：
| 本题精髓在于对标记访问数组visited值的扩展，常规0 | 1标记是否访问，但还需要记录走到当前位置所剩的消除障碍物次数，越多越好。因为后面的路障谁都不清楚够不够用。 |
visited访问标记数组二维 + 贪心 （推荐）
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Solution {
// 这个类的创建与否不影响
class Point {
int x;
int y;
int oneCount;
public Point(int x, int y, int oneCount) {
this.x = x;
this.y = y;
this.oneCount = oneCount;
}
}
public int shortestPath(int[][] grid, int k) {
int rows = grid.length;
int cols = grid[0].length;
// 非法参数处理
if (validateInputParams(k, rows, cols)) {
return -1;
}
// 特殊场景处理
if (rows == 1 && cols == 1) {
return 0;
}
// BFS对于当前点的下一个点选择，如果grid[i][j]=0则有效入队列 visited[i][j]记录消除障碍次数
// 若grid[i][j]=1则看是否还有消除障碍机会，若没有 此点丢弃
// 若有消除障碍机会， （上一个点剩余消除障碍机会 - 1）比visited[i][j] 值比大 此点入队， 小则丢弃（贪心）
// 例子：k=1, 坐标(0,2)可以为消除(0,1)障碍过来的 visited[0][2] = 0，搜索层级为2
// 也可能为不消除任何障碍过来的 visited[0][2] = 1，层级为6，更新visited[0][2] = 1并入队
// 因为到后面还需要消除障碍才能到达目标，先消除障碍走到visited[0][2] = 0的肯定到不了目标...
// 0 1 0 0 0 1 0 0
// 0 1 0 1 0 1 0 1
// 0 0 0 1 0 0 1 0
// 二维标记数组初始状态为-1，值记录剩余消除障碍的次数，剩余次数越多 越有价值（此处贪心，记录局部最优）
int[][] visited = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
visited[i][j] = -1;
}
}
// 初始步数为0，rows=cols=1的特殊场景已处理
int minSteps = 0;
// 初始位置标记已访问,值记录剩余消除障碍物次数 越多越好
// 1. 对于其他路径到达此点且剩余消除障碍物次数小于等于当前值 —— 剪枝
// 2. 对于其他路径到达此点且剩余消除障碍物次数大于当前值 —— 取代并入队
visited[0][0] = k;
Queue<Point> queue = new LinkedList<>();
Point startPoint = new Point(0, 0, 0);
queue.offer(startPoint);
// 定义四个方向移动坐标
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
// BFS搜索-队列遍历
while (!queue.isEmpty()) {
minSteps++;
// BFS搜索-遍历相同层级下所有节点
// 当前队列长度一定要在循环外部定义，循环内部有插入对列操作
int size = queue.size();
for (int i = 0; i < size; i++) {
Point current = queue.poll();
int x = current.x;
int y = current.y;
int oneCount = current.oneCount;
// 对当前节点四个方向进行识别处理
for (int j = 0; j < 4; j++) {
int newX = x + dx[j];
int newY = y + dy[j];
// 越界判断
if (newX < 0 || newX >= rows || newY < 0 || newY >= cols) {
continue;
}
// 搜索到目标节点直接返回结果，按层级就是最短步数
if (newX == rows - 1 && newY == cols - 1) {
return minSteps;
}
// 穿越障碍次数已满
if (grid[newX][newY] == 1 && oneCount >= k) {
continue;
}
int oneCountNew = grid[newX][newY] == 1 ? oneCount + 1 : oneCount;
// 剪枝 - 节点已被访问过，且当前visited记录的剩余障碍物消除次数 >= 当前搜索节点层级的剩余消除次数
if (visited[newX][newY] != -1 && visited[newX][newY] >= k - oneCountNew) {
continue;
} else {
// 否则，贪心将最优值更新，并将该层级节点入队
visited[newX][newY] = k - oneCountNew;
}
queue.offer(new Point(newX, newY, oneCountNew));
}
}
}
// BFS没搜索到目标，返回-1
return -1;
}
private boolean validateInputParams(int k, int m, int n) {
return m > 40 || m < 1 || n > 40 || n < 1 || k < 1 || k > m * n;
}
}
障碍物且可以有k次机会消除，单纯有障碍物就是标准的BFS处理即可，但有k次消除障碍物，就需要增加一个维度来记录同一个节点被访问的时候 已经使用消除障碍物的次数。
visited访问标记数组三维扩展 （用于比较）
1