• ㊗️
• 大家
• offer
• 多多！

## 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]]


Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^4
• 1 <= m * n <= 10^4
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

## Code

64. Minimum Path Sum

BFS

class Solution {
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;

Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[m][n];

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

int step = 1;
while (!queue.isEmpty()) {
int size = queue.size();

for (int i = 0; i < size; i++) {
int[] curr = queue.poll();

for (int[] dir : dirs) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];

if (x < 0 || x >= m || y < 0 || y >= n) continue;
if (visited[x][y]) continue;

matrix[x][y] = step;
visited[x][y] = true;
queue.offer(new int[]{x, y});
}
}

step++;
}

return matrix;
}
}


class Solution {
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;

int[][] dp = new int[m][n];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
dp[i][j] = 0;
} else {
dp[i][j] = m + n;
}
}
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i != 0) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
}

if (j != 0) {
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
}
}
}

for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i != m - 1) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
}

if (j != n - 1) {
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
}
}
}

return dp;
}
}