542. 01 Matrix (Medium)

https://leetcode.com/problems/01-matrix/

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

0 0 0
0 1 0
1 2 1

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

Solutions

class Solution {
    private class Node {
        int row;
        int col;
        int distance;

        Node(int r, int c) {
            this.row = r;
            this.col = c;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }

            if (!(o instanceof Node)) {
                return false;
            }

            Node node = (Node) o;

            return row == node.row && col == node.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
    }

    private final int[] R = {0, 0, 1, -1};
    private final int[] C = {1, -1, 0, 0};

    private Set<Node> done = new HashSet<>();
    private Queue<Node> queue = new ArrayDeque<>();

    public int[][] updateMatrix(int[][] matrix) {
        int[][] temp = new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                temp[i][j] = matrix[i][j];

                // ignore all the cells with 1
                if (matrix[i][j] != 0) {
                    continue;
                }

                // register all the cells of 0 value
                Node node = new Node(i, j);

                queue.offer(node);

                done.add(node);
            }
        }

        // elements in queue are kept in ascending order by node.distance
        // shorter distance nodes are always handled at first, then the longer distance.
        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            for (int i = 0; i < 4; i++) {
                int newR = curr.row + R[i];
                int newC = curr.col + C[i];

                // out of the boundary
                if (newR < 0 || newR >= matrix.length || newC < 0 || newC >= matrix[0].length) {
                    continue;
                }

                // the next node near this one
                Node child = new Node(newR, newC);

                // ignore already computed cell
                // actually, nodes in done queue are of optimal distances
                // other paths may lead to this node, however not the prime
                // because of the trait of the queue
                if (done.contains(child)) {
                    continue;
                }

                done.add(child);

                child.distance = curr.distance + 1;
                temp[newR][newC] = child.distance;

                queue.offer(child);
            }
        }

        return temp;
    }
}

Incorrect Solutions

References