Как избежать бесконечного цикла в BFS? - PullRequest
Новая
       4

Как избежать бесконечного цикла в BFS?

0 голосов
/ 07 января 2019

Вот проблема LeetCode 542. 01 Матрица

Мой код создаст бесконечный цикл, потому что он будет выдвигать все направления в очередь, даже если этот узел уже был посещен. Я не могу придумать способ решить эту проблему. Может ли кто-нибудь помочь? 

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;
}
}

Ответы [ 2 ]

0 голосов
/ 07 января 2019

Инкапсулируйте адрес узла в классе, который может реализовать хэш-код и равно, как предложено в этом ответе. Класс узла может быть таким простым: 

class Node {

    private final int[] address;
    Node(int[] address){
        this.address = address;
    }

    @Override
    public boolean equals(Object other) {
        if(other == null ||!(other instanceof Node)) return false;
        return Arrays.equals(address, ((Node)other).getAddress());
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(address);
    }

    public int[] getAddress() {
        return address;
    }
}

Позволяет поддерживать коллекцию посещенных узлов: Set<Node> visited = new HashSet<>();
Когда visited.add(node) возвращает false, вы знаете, что visited уже содержит node

0 голосов
/ 07 января 2019

Вы должны отслеживать уже посещенные узлы. Вы можете оставить узлы в списке или переместить их в отдельный 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?

Я оставлю это как упражнение.

...