Странное поведение приоритетов приоритет, когда порядок сортировки получен из Hashmap ⇐ JAVA

[Anonymous]

Во время работы в LeetCode 675 я наткнулся на странное поведение с приоритетом компаратором , который я не могу объяснить. Заинтересованные стороны могут прочитать его на LeetCode подробно. Попрос - найти минимальное количество шагов для посещения (отключить) все ячейки деревьев в порядке возрастания высот деревьев. Затем я рассчитываю минимальное расстояние от каждого дерева до его следующего, выполнив поиск A*, используя эвристическую функцию: расстояние от источника + расстояние Манхэттана от цели < /code> < /p>
Минимальное количество шагов для отключения всех деревьев - это сумма всех расстояний A*. Class = "Lang-Java PrettyPrint-Override">

Код: Выделить всё

class Solution {
private final int[][] dx = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int cutOffTree(List 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 getTreesSortedByHeight(List forest) {
List 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 forest, int[] start, int[] goal) {
int m = forest.size();
int n = forest.get(0).size();
Map 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 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);
}
}

Обратите внимание, что каждая запись в куче содержит эвристические затраты . Логически, это ненужная , потому что запись также содержит координаты ячейки (строка и столбец), используя, что мы можем извлечь расстояние из карты затрат следующим образом:
Queue heap = new PriorityQueue(Comparator.comparingInt(a -> costs.get(a[1] * n + a[2]);
< /code>

В отсутствие стоимости вход в кучу состоит из [расстояния, строки, столбца]. < /li>
< /ul>
Но это не работает < /strong> и терпит неудачу в одном из тестовых случаев. Тестовый пример огромен, поэтому я не вижу смысла вставать на его здесь, так как вряд ли у кого -то будет время отладить его.>

Подробнее здесь: https://stackoverflow.com/questions/795 ... om-hashmap