# 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 0
```
Output:
```0 0 0
0 1 0
0 0 0
```

Example 2:
Input:

```0 0 0
0 1 0
1 1 1
```
Output:
```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);

}
}

// 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);

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

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

queue.offer(child);
}
}

return temp;
}
}
``````