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.
The distance between two adjacent cells is 1.Example 1:
Input:
0 0 0 0 1 0 0 0 0Output:
0 0 0 0 1 0 0 0 0
Example 2:
Input:
0 0 0 0 1 0 1 1 1Output:
0 0 0 0 1 0 1 2 1
Note:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- 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;
}
}