Voici le problème LeetCode 542. 01 Matrix
Mon code créera une boucle infinie car il poussera toutes les directions dans la file d'attente, même si ce nœud a déjà été visité. Je ne peux pas penser à un moyen de résoudre ce problème. Quelqu'un pourrait-il aider?
class Solution {
int[][] dirs = { {0,1},{0,-1},{1,0},{-1,0} };
public int[][] updateMatrix(int[][] matrix) {
for(int i=0;i < matrix.length;i++){
for(int j=0; j < matrix[i].length;j++){
if(matrix[i][j] == 1)
matrix[i][j] = Integer.MAX_VALUE;
BFS(new int[]{i,j},matrix);
}
}
return matrix;
}
public void BFS(int[] node,int[][] matrix){
if(matrix[node[0]][node[1]] == 0)
return;
LinkedList<int[]> queue = new LinkedList<>();
queue.push(node);
int step = 1;
while(!queue.isEmpty()){
int[] temp = queue.poll();
if(temp == null){
step++;
continue;
}
for(int[] dir:dirs){
int r = temp[0] + dir[0];
int c = temp[1] + dir[1];
if(r < 0 || c < 0 || r >= matrix.length || c >= matrix[r].length)
continue;
queue.push(new int[] {r,c});
if(matrix[r][c] == 0){
matrix[temp[0]][temp[1]] = Math.min(step,matrix[temp[0]][temp[1]]);
}
}
queue.push(null);
}
return;
}
}
Vous devez garder une trace des nœuds qui ont déjà été visités. Vous pouvez soit conserver les nœuds dans la liste, soit les déplacer vers un autre Set.
Le problème que vous rencontrez ici est que les nœuds sont des tableaux et que vous ne pouvez pas les utiliser dans un fichier HashSet. Je commencerais par déclarer une classe Coordinates:
public class Coordinates {
public final int row;
public final int col;
public Coordinates(int r, int c) {
this.row = r;
this.col = c;
}
@Override
public int hashCode() {
return (row + 37*col) & 0x7FFFFFFF;
}
@Override
public boolean equals(Object other) {
if (other == null || other.getClass() != getClass()) {
return false;
}
Coordinates o = (Coordinates)other;
return row == o.row && col == o.col;
}
}
Option 1: garder les nœuds dans la file d'attente
Je n'ai pas compris le but d'ajouter des nulls dans la file d'attente; Je viens de supprimer ceci.
public void BFS(Coordinates node,int[][] matrix){
if(matrix[node.row][node.col] == 0)
return;
List<Coordinates> queue = new ArrayList<>();
queue.add(node);
for (int i = 0; i < queue.size(); ++i) {
Coordinates temp = queue.get(i);
for(int[] dir:dirs){
int r = temp.row + dir.row;
int c = temp.col + dir.col;
if(r < 0 || c < 0 || r >= matrix.length || c >= matrix[r].length)
continue;
Coordinates newCoord = new Coordinates(r, c);
if (!queue.contains(newCoord)) {
queue.add(newCoord);
}
if(matrix[r][c] == 0){
matrix[temp.row][temp.col] = Math.min(step,matrix[temp.row][temp.col]);
}
}
}
return;
}
Option 2: utiliser un Set
Maintenant que nous avons hashCodeune equalsméthode et une , pourquoi ne pas utiliser une HashSet?
Je laisserai cela comme un exercice.
Cet article est collecté sur Internet, veuillez indiquer la source lors de la réimpression.
En cas d'infraction, veuillez [email protected] Supprimer.
laisse moi dire quelques mots