## Algorithm

Problem Name: 542. 01 Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[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 <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

class Solution {
public:
vector<vector<int>> updateMatrix(vector < vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector < pair<int, int>>dir({{0, 1}, {1, 0}, {-1, 0}, {0, -1}});
deque < pair<int, int>>q;
for(int i = 0; i  <  m; i++)
for(int j = 0; j  <  n; j++)
if(matrix[i][j]) matrix[i][j] = INT_MAX;
else q.push_back({i, j});
//BFS
while(!q.empty()){
auto p = q.front();
q.pop_front();
for(auto x: dir){
int r = p.first + x.first;
int c = p.second + x.second;
if(r < 0 || c  <  0 || r == m || c == n> continue;
if(matrix[r][c] >= matrix[p.first][p.second] + 1){
matrix[r][c] = matrix[p.first][p.second] + 1;
q.push_back({r, c});
}
}
}
return matrix;
}
};
Copy The Code &

Input

cmd
mat = [[0,0,0],[0,1,0],[0,0,0]]

Output

cmd
[[0,0,0],[0,1,0],[0,0,0]]

### #2 Code Example with Java Programming

Code - Java Programming

class Solution {
private static final int[][] DIRS = {{1, 0},  {0, 1}, {-1, 0}, {0, -1}};

public int[][] updateMatrix(int[][] mat) {
int numRows = mat.length;
int numCols = mat[0].length;
int[][] distances = new int[numRows][numCols];
Queue < int[]> queue = new LinkedList<>();
for (int i = 0; i  <  numRows; i++) {
for (int j = 0; j  <  numCols; j++) {
if (mat[i][j] == 0) {
} else {
distances[i][j] = Integer.MAX_VALUE;
}
}
}
while (!queue.isEmpty()) {
int[] removed = queue.remove();
int currX = removed[0];
int currY = removed[1];
for (int[] dir : DIRS) {
int newX = currX + dir[0];
int newY = currY + dir[1];
if (newX >= 0 && newY >= 0 && newX  <  numRows && newY < numCols && distances[newX][newY] > distances[currX][currY] + 1) {
distances[newX][newY] = distances[currX][currY] + 1;
}
}
}
return distances;
}
}
Copy The Code &

Input

cmd
mat = [[0,0,0],[0,1,0],[0,0,0]]

Output

cmd
[[0,0,0],[0,1,0],[0,0,0]]

### #3 Code Example with Javascript Programming

Code - Javascript Programming

const updateMatrix = function (matrix) {
const rows = matrix.length, cols = matrix[0].length;
const maxDist = rows + cols;
let dist = new Array(rows).fill(null).map(() => new Array(cols).fill(0));

for (let i = 0; i  <  rows; i++) {
for (let j = 0; j  <  cols; j++) {
if (matrix[i][j] !== 0) {
dist[i][j] = hasNeighborZero(i, j, matrix, rows, cols) ? 1 : maxDist;
}
}
}

for (let i = 0; i  <  rows; i++) {
for (let j = 0; j  <  cols; j++) {
if (dist[i][j] === 1) {
dfs(dist, i, j, -1);
}
}
}

return dist;
};

const dfs = function (dist, row, col, step) {
if (row  <  0 || row >= dist.length || col < 0 || col >= dist[0].length || dist[row][col] <= step) return;

if (step > 0) dist[row][col] = step;

dfs(dist, row + 1, col, dist[row][col] + 1);
dfs(dist, row - 1, col, dist[row][col] + 1);
dfs(dist, row, col + 1, dist[row][col] + 1);
dfs(dist, row, col - 1, dist[row][col] + 1);
};

const hasNeighborZero = function (row, col, matrix, rows, cols) {
if (row  <  rows - 1 && matrix[row + 1][col] === 0) return true;
if (row > 0 && matrix[row - 1][col] === 0) return true;
if (col > 0 && matrix[row][col - 1] === 0) return true;
if (col  <  cols - 1 && matrix[row][col + 1] === 0) return true;

return false;
};
Copy The Code &

Input

cmd
mat = [[0,0,0],[0,1,0],[1,1,1]]

Output

cmd
[[0,0,0],[0,1,0],[1,2,1]]

### #4 Code Example with Python Programming

Code - Python Programming

class Solution:
def updateMatrix(self, matrix):
m, n = len(matrix), len(matrix and matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] != 0:
matrix[i][j] = float("inf")
if i > 0 and matrix[i - 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i - 1][j] + 1
if j > 0 and matrix[i][j - 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j - 1] + 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if matrix[i][j] != 0:
if i + 1 < m and matrix[i + 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i + 1][j] + 1
if j + 1 < n and matrix[i][j + 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j + 1] + 1
return matrix
Copy The Code &

Input

cmd
mat = [[0,0,0],[0,1,0],[1,1,1]]

Output

cmd
[[0,0,0],[0,1,0],[1,2,1]]