题目形容
这是 LeetCode 上的 675. 为高尔夫较量砍树 ，难度为 艰难。
Tag :「图论 BFS」、「AStar 算法」、「启发式搜寻」、「并查集」
你被请来给一个要举办高尔夫较量的树林砍树。树林由一个 $m \times n$ 的矩阵示意，在这个矩阵中：
- $0$ 示意阻碍，无奈触碰
- $1$ 示意高空，能够行走
- 比 $1$ 大的数 示意有树的单元格，能够行走，数值示意树的高度
每一步，你都能够向上、下、左、右四个方向之一挪动一个单位，如果你站的中央有一棵树，那么你能够决定是否要砍倒它。
你须要依照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 $1$（即变为高空）。
你将从 $(0, 0)$ 点开始工作，返回你砍完所有树须要走的最小步数。如果你无奈砍完所有的树，返回 $-1$。
能够保障的是，没有两棵树的高度是雷同的，并且你至多须要砍倒一棵树。
示例 1：
输出：forest = [[1,2,3],[0,0,4],[7,6,5]]
输入：6
解释：沿着下面的门路，你能够用 6 步，按从最矮到最高的程序砍掉这些树。示例 2：
输出：forest = [[1,2,3],[0,0,0],[7,6,5]]
输入：-1
解释：因为两头一行被阻碍阻塞，无法访问最上面一行中的树。示例 3：
输出：forest = [[2,3,4],[0,0,5],[8,7,6]]
输入：6
解释：能够按与示例 1 雷同的门路来砍掉所有的树。(0,0) 地位的树，能够间接砍去，不必算步数。提醒：
- $m == forest.length$
- $n == forest[i].length$
- $1 <= m, n <= 50$
- $0 <= forest[i][j] <= 10^9$
根本剖析
根本题意为：给定一个 $n \times m$ 的矩阵，每次可能在以后地位往「四联通」挪动一个单位，其中 $0$ 的地位代表阻碍（无法访问），$1$ 的地位代表高山（可间接拜访，且毋庸进行任何决策），其余大于 $1$ 的地位代表有树，通过该地位的时候能够思考将树砍掉（相应值变为高山 $1$）。
同时题目限定了咱们只能依照「从低到高」的程序进行砍树，并且图中不存在高度相等的两棵树，这意味着 整个砍树的程序惟一确定，就是对所有有树的中央进行「高度」排升序，即是残缺的砍树路线。
而另外一个更为重要的性质是：点与点之间的最短门路，不会随着砍树过程的进行而发生变化（某个树点被砍掉，只会变为高山，不会变为妨碍点，仍可通过）。
综上，砍树的路线惟一确定，当咱们求出每两个相邻的砍树点最短门路，并进行累加即是答案（整条砍树门路的起码步数）。
BFS
因而，再联合数据范畴只有 $50$，并且点与点之间边权为 $1$（每次挪动算一步），咱们能够间接进行 BFS 进行求解。
先对整张图进行一次遍历，预处理出所有的树点（以三元组 $(height, x, y)$ 的模式进行存储），并对其以 $height$ 排升序，失去惟一确定的砍树门路。
之后就是计算砍树门路中相邻点的最短距离，使用 BFS 求解任意两点的最短门路复杂度为 $O(n \times m)$，咱们最多有 $n \times m$ 个树点，因而整体复杂度为 $O(n^2 * \times m^2)$。
求解相邻点的最短距离的局部也是整个算法的复杂度上界，数据范畴只有 $50$，计算量不超过 $10^7$，能够过。
代码：
class Solution {
int N = 50;
int[][] g = new int[N][N];
int n, m;
List<int[]> list = new ArrayList<>();
public int cutOffTree(List<List<Integer>> forest) {n = forest.size(); m = forest.get(0).size();
for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {g[i][j] = forest.get(i).get(j);
if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
}
}
Collections.sort(list, (a,b)->a[0]-b[0]);
if (g[0][0] == 0) return -1;
int x = 0, y = 0, ans = 0;
for (int[] ne : list) {int nx = ne[1], ny = ne[2];
int d = bfs(x, y, nx, ny);
if (d == -1) return -1;
ans += d;
x = nx; y = ny;
}
return ans;
}
int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
int bfs(int X, int Y, int P, int Q) {if (X == P && Y == Q) return 0;
boolean[][] vis = new boolean[n][m];
Deque<int[]> d = new ArrayDeque<>();
d.addLast(new int[]{X, Y});
vis[X][Y] = true;
int ans = 0;
while (!d.isEmpty()) {int size = d.size();
while (size-- > 0) {int[] info = d.pollFirst();
int x = info[0], y = info[1];
for (int[] di : dirs) {int nx = x + di[0], ny = y + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (g[nx][ny] == 0 || vis[nx][ny]) continue;
if (nx == P && ny == Q) return ans + 1;
d.addLast(new int[]{nx, ny});
vis[nx][ny] = true;
}
}
ans++;
}
return -1;
}
}- 工夫复杂度：预处理出所有树点的复杂度为 $O(n \times m)$，对树点进行排序的复杂度为 $O(nm \log{nm})$，最多有 $n \times m$ 个树点，对每两个相邻树点使用
BFS求最短路的复杂度为 $O(n \times m)$，统计残缺门路的复杂度为 $O(n^2 \times m^2)$ - 空间复杂度：$O(n \times m)$
AStar 算法
因为问题的实质是求最短路，同时原问题的边权为 $1$，因而套用其余复杂度比 BFS 高的最短路算法，对于本题而言是没有意义，但使用启发式搜寻 AStar 算法来优化则是有意义。
因为在 BFS 过程中，咱们会无差别往「四联通」方向进行搜寻，直到找到「以后树点的下一个指标地位」为止，而实际上，两点之间的最短门路往往与两点之间的绝对地位相干。
举个 🌰，以后咱们在地位 $S$，咱们指标地位是 $T$，而 $T$ 在 $S$ 的右下方，此时咱们该当优先搜寻方向 ” 往右下方 ” 的门路，当无奈从 ” 往右下方 ” 的门路达到 $T$，咱们再思考搜寻其余大方向的门路：
如何设计这样带有优先级的搜寻程序，则是 AStar 算法「启发式函数」的设计过程，其本质是对应了对「最小步数」的估算，只有当咱们确保「最小步数估算 $\leq $ 理论最小步数」，AStar 算法的正确性才得以保障。
因而咱们往往会间接应用「实践最小步数」来作为启发式函数的，对于本题，可间接应用「曼哈顿间隔」作为「实践最小步数」。
因而，如果咱们是要从源点 $S$ 到汇点 $T$，并且以后位于中途点 $x$ 的话，点 $x$ 的最小步数估算包含两局部：到点 $x$ 的理论步数 + 从点 $x$ 到点 $T$ 的实践最小步数（曼哈顿间隔）。应用「优先队列」依照「总的最小步数估算」进行出队，即可实现 AStar 算法的搜寻程序。
AStar 算法做过很屡次了，相干合集能够在 这里 看到。
另外，网上很多对 AStar 正确性证实不理解的人，会短少以下map.get(nidx) > step + 1判断逻辑。
简略来说，启发式函数的设计是针对汇点而言的，因而 AStar 算法搜寻过程只确保对 $T$ 的出入队秩序可能对应回到点 $T$ 第 $k$ 短路，而对于其余点的出入队秩序到其余点的最短路没有必然的对应关系，因而当某个点的最小步数被更新，咱们是要将其进行再次入队的。
代码：
class Solution {
int N = 50;
int[][] g = new int[N][N];
int n, m;
List<int[]> list = new ArrayList<>();
public int cutOffTree(List<List<Integer>> forest) {n = forest.size(); m = forest.get(0).size();
for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {g[i][j] = forest.get(i).get(j);
if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
}
}
if (g[0][0] == 0) return -1;
Collections.sort(list, (a,b)->a[0]-b[0]);
int x = 0, y = 0, ans = 0;
for (int[] ne : list) {int nx = ne[1], ny = ne[2];
int d = astar(x, y, nx, ny);
if (d == -1) return -1;
ans += d;
x = nx; y = ny;
}
return ans;
}
int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
int getIdx(int x, int y) {return x * m + y;}
int f(int X, int Y, int P, int Q) {return Math.abs(X - P) + Math.abs(Y - Q);
}
int astar(int X, int Y, int P, int Q) {if (X == P && Y == Q) return 0;
Map<Integer, Integer> map = new HashMap<>();
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
q.add(new int[]{f(X, Y, P, Q), X, Y});
map.put(getIdx(X, Y), 0);
while (!q.isEmpty()) {int[] info = q.poll();
int x = info[1], y = info[2], step = map.get(getIdx(x, y));
for (int[] di : dirs) {int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (g[nx][ny] == 0) continue;
if (nx == P && ny == Q) return step + 1;
if (!map.containsKey(nidx) || map.get(nidx) > step + 1) {q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny});
map.put(nidx, step + 1);
}
}
}
return -1;
}
}- 工夫复杂度：启发式搜寻剖析时空复杂度意义不大
- 空间复杂度：启发式搜寻剖析时空复杂度意义不大
AStar 算法 + 并查集预处理无解
咱们晓得，AStar 算法应用到了「优先队列（堆）」来进行启发式搜寻，而对于一些最佳门路方向与两点绝对地位相同（例如 $T$ 在 $S$ 的左边，但因为存在阻碍，最短门路须要先从右边绕一圈能力到 $T$），AStar 反而会因为优先队列（堆）而多一个 $\log$ 的复杂度。
因而一个可行的优化是，咱们先提前解决「无解」的状况，常见的做法是在预处理过程中使用「并查集」来保护连通性。
这种对于不影响复杂度上界的预处理相比后续可能呈现的大量有效搜寻（最终无解）的计算量而言，是无益的。
代码：
class Solution {
int N = 50;
int[][] g = new int[N][N];
int n, m;
int[] p = new int[N * N + 10];
List<int[]> list = new ArrayList<>();
void union(int a, int b) {p[find(a)] = p[find(b)];
}
boolean query(int a, int b) {return find(a) == find(b);
}
int find(int x) {if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int getIdx(int x, int y) {return x * m + y;}
public int cutOffTree(List<List<Integer>> forest) {n = forest.size(); m = forest.get(0).size();
// 预处理过程中，同时应用「并查集」保护连通性
for (int i = 0; i < n * m; i++) p[i] = i;
int[][] tempDirs = new int[][]{{0,-1},{-1,0}};
for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {g[i][j] = forest.get(i).get(j);
if (g[i][j] > 1) list.add(new int[]{g[i][j], i, j});
if (g[i][j] == 0) continue;
// 只与左方和上方的区域联通即可确保不重不漏
for (int[] di : tempDirs) {int nx = i + di[0], ny = j + di[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (g[nx][ny] != 0) union(getIdx(i, j), getIdx(nx, ny));
}
}
}
// 若不满足所有树点均与 (0,0)，提前返回无解
for (int[] info : list) {int x = info[1], y = info[2];
if (!query(getIdx(0, 0), getIdx(x, y))) return -1;
}
Collections.sort(list, (a,b)->a[0]-b[0]);
int x = 0, y = 0, ans = 0;
for (int[] ne : list) {int nx = ne[1], ny = ne[2];
int d = astar(x, y, nx, ny);
if (d == -1) return -1;
ans += d;
x = nx; y = ny;
}
return ans;
}
int f(int X, int Y, int P, int Q) {return Math.abs(X - P) + Math.abs(Y - Q);
}
int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
int astar(int X, int Y, int P, int Q) {if (X == P && Y == Q) return 0;
Map<Integer, Integer> map = new HashMap<>();
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
q.add(new int[]{f(X, Y, P, Q), X, Y});
map.put(getIdx(X, Y), 0);
while (!q.isEmpty()) {int[] info = q.poll();
int x = info[1], y = info[2], step = map.get(getIdx(x, y));
for (int[] di : dirs) {int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (g[nx][ny] == 0) continue;
if (nx == P && ny == Q) return step + 1;
if (!map.containsKey(nidx) || map.get(nidx) > step + 1) {q.add(new int[]{step + 1 + f(nx, ny, P, Q), nx, ny});
map.put(nidx, step + 1);
}
}
}
return -1;
}
}- 工夫复杂度：启发式搜寻剖析时空复杂度意义不大
- 空间复杂度：启发式搜寻剖析时空复杂度意义不大
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.675 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干的材料可拜访排版精明的 合集新基地 🎉🎉
本文由 mdnice 多平台公布