在学习LeetCode 675时，我遇到了一种PriorityQueue Comparator无法解释的奇怪行为。
为了简洁起见，我将陈述问题陈述的要点；感兴趣的人可以在 LeetCode 上阅读全文。
给定一个名为 的 mxn 矩阵
forest，其中某些单元格被指定为trees。问题是找到按树高升序访问（截断）所有树单元格所需的最少步数。
为了解决这个问题，我找到了所有的树，并按高度升序排列。然后，我使用启发式函数运行 A* 搜索，计算每棵树到下一棵树的最小距离：distance from source + Manhattan distance from the goal
切断所有树的最小步数是所有 A* 距离的总和。如果 A* 搜索在任何时候未能返回路径，我就中止搜索。
class Solution {
private final int[][] dx = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int cutOffTree(List<List<Integer>> forest) {
int[] curr = new int[] {0, 0};
int dist = 0;
for (int[] next : getTreesSortedByHeight(forest)) {
int d = minDist(forest, curr, next);
if (d < 0) {
return -1;
}
curr = next;
dist += d;
}
return dist;
}
private List<int[]> getTreesSortedByHeight(List<List<Integer>> forest) {
List<int[]> trees = new ArrayList<>();
for (int row = 0; row < forest.size(); row++) {
for (int col = 0; col < forest.get(0).size(); col++) {
if (forest.get(row).get(col) > 1) {
trees.add(new int[] {row, col});
}
}
}
trees.sort(Comparator.comparingInt(a -> forest.get(a[0]).get(a[1])));
return trees;
}
int minDist(List<List<Integer>> forest, int[] start, int[] goal) {
int m = forest.size();
int n = forest.get(0).size();
Map<Integer, Integer> costs = new HashMap<>();
costs.put(start[0] * n + start[1], manhattanDist(start[0], start[1], goal));
// GOTCHA: Fetching the distance from the cost map using the coordinates doesn't work!
Queue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
heap.offer(new int[] {0, 0, start[0], start[1]}); // [cost, distance, row, column]
while (!heap.isEmpty()) {
int[] curr = heap.poll();
int dist = curr[1];
int row = curr[2];
int col = curr[3];
if (row == goal[0] && col == goal[1]) {
return dist;
}
for (int[] d : dx) {
int r = row + d[0];
int c = col + d[1];
if (r >= 0 && r < m && c >= 0 && c < n && forest.get(r).get(c) > 0) {
int cost = dist + 1 + manhattanDist(r, c, goal);
if (cost < costs.getOrDefault(r * n + c, Integer.MAX_VALUE)) {
costs.put(r * n + c, cost);
heap.offer(new int[] {cost, dist + 1, r, c});
}
}
}
}
return -1;
}
private int manhattanDist(int row, int col, int[] goal) {
return Math.abs(goal[0] - row) + Math.abs(goal[1] - col);
}
}
请注意，每个堆条目都包含启发式成本。从逻辑上讲，这是不必要的，因为条目还包含单元格坐标（行和列），我们可以使用这些坐标从地图中获取距离costs，如下所示：
Queue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> costs.get(a[1] * n + a[2]);
- 在没有成本的情况下，堆条目由[距离，行，列]组成。
但这不起作用，并且其中一个测试用例失败了。这个测试用例太大了，所以我觉得没有必要贴在这里，毕竟不太可能有人有时间去调试它。
我想知道为什么会出现这种奇怪的现象。
编辑： 根据评论中的要求添加了完整的代码。
