Вы должны отслеживать уже посещенные узлы. Вы можете оставить узлы в списке или переместить их в отдельный Set
.
Проблема, с которой вы здесь столкнулись, заключается в том, что узлы являются массивами, и вы не можете использовать их в HashSet
. Я бы начал с объявления класса 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;
}
}
Вариант 1: сохранение узлов в очереди
Я не понял цели добавления null
s в очередь; Я только что удалил это.
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;
}
Вариант 2: использовать отдельный Set
Теперь, когда у нас есть hashCode
и equals
метод, почему бы не использовать HashSet
?
Я оставлю это как упражнение.