# Simple BFS idea

• modified to be more concise

public class Solution {
private int[][] dirs = {{1,0},{-1,0},{0,-1},{0,1}};
private int m, n;
public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
List<List<Integer>> res = new ArrayList<>();
if (matrix == null || matrix.size() == 0 || matrix.get(0).size() == 0) return res;
m = matrix.size();
n = matrix.get(0).size();
boolean[][] visited = new boolean[m][n];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix.get(i).get(j) == 0) {
visited[i][j] = true;
queue.offer(new int[]{i, j});
}
}
}

while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int[] dir : dirs) {
int nx = curr[0] + dir[0], ny = curr[1] + dir[1];
if (nx < 0 || ny < 0 || nx >= m || ny >= n || visited[nx][ny]) continue;
visited[nx][ny] = true;
int dist = matrix.get(curr[0]).get(curr[1]);
matrix.get(nx).set(ny, dist + 1);
queue.offer(new int[]{nx, ny});
}
}
return matrix;
}
}

[old version] not concise since I treat the input matrix as immutable.

public class Solution {
private int[][] dirs = {{1,0},{-1,0},{0,-1},{0,1}};
private int m, n;
public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
List<List<Integer>> res = new ArrayList<>();
if (matrix == null || matrix.size() == 0 || matrix.get(0).size() == 0) return res;
m = matrix.size();
n = matrix.get(0).size();
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (valid(matrix, i, j)) {
visited[i][j] = true;
queue.offer(new int[]{i, j});
}
}
}
int dist = 0;
while (!queue.isEmpty()) {
int size = queue.size();
dist++;
for (int i = 0; i < size; i++) {
int[] point = queue.poll();
res.get(point[0]).set(point[1], dist);
for (int[] dir : dirs) {
int nx = point[0] + dir[0];
int ny = point[1] + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix.get(nx).get(ny) == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
}
return res;
}
private boolean valid(List<List<Integer>> matrix, int i, int j) {
if (matrix.get(i).get(j) == 0) return false;
else {
if (i > 0 && matrix.get(i - 1).get(j) == 0) return true;
if (i < m - 1 && matrix.get(i + 1).get(j) == 0) return true;
if (j > 0 && matrix.get(i).get(j - 1) == 0) return true;
if (j < n - 1 && matrix.get(i).get(j + 1) == 0) return true;
}
return false;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.