542. 01 Matrix
Problem:
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:
- 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:
public class Solution {
public int[][] updateMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return matrix;
}
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
Queue<Integer> qx = new LinkedList<Integer>();
Queue<Integer> qy = new LinkedList<Integer>();
for (int i = 0; i < matrix.length; i ++) {
for (int j = 0; j < matrix[0].length; j ++) {
if (matrix[i][j] == 0) {
qx.add(i);
qy.add(j);
}
else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
while (!qx.isEmpty()) {
int x = qx.poll();
int y = qy.poll();
for (int i = 0; i < dirs.length; i ++) {
int nx = x + dirs[i][0];
int ny = y + dirs[i][1];
if (nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && matrix[nx][ny] > matrix[x][y] + 1) {
matrix[nx][ny] = matrix[x][y] + 1;
qx.add(nx);
qy.add(ny);
}
}
}
return matrix;
}
}