Enquanto trabalhava no LeetCode 675 , me deparei com um comportamento estranho PriorityQueue Comparatorque não consigo explicar.
Para resumir, vou apresentar a essência da declaração do problema; os interessados podem lê-la em detalhes no LeetCode.
Dada uma matriz mxn chamada
forest, algumas células são designadas comotrees. O desafio é encontrar o número mínimo de passos para visitar (cortar) todas as células da árvore, em ordem crescente de altura da árvore.
Para resolver isso, encontro todas as árvores e as ordeno em ordem crescente de altura. Em seguida, calculo a distância mínima de cada árvore até a próxima executando uma busca A* usando a função heurística:distance from source + Manhattan distance from the goal
O número mínimo de passos para cortar todas as árvores é a soma de todas as distâncias A*. Se em algum momento a busca A* não retornar um caminho, eu aborto.
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);
}
}
Observe que cada entrada de heap contém o custo heurístico . Logicamente, isso é desnecessário , pois a entrada também contém as coordenadas da célula (linha e coluna), com as quais podemos obter a distância do costsmapa da seguinte maneira:
Queue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> costs.get(a[1] * n + a[2]);
- Na ausência do custo, a entrada do heap consiste em [distância, linha, coluna].
Mas isso não funciona e falha em um dos casos de teste. O caso de teste é enorme, então não vejo sentido em colá-lo aqui, pois é improvável que alguém tenha tempo para depurá-lo.
O que eu gostaria de saber é o porquê dessa estranheza.
Editar: código completo adicionado conforme solicitado em um comentário.
