01 Matrix Problem
Description
LeetCode Problem 542.
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:
1
2
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Example 2:
1
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 <= 10^4
- 1 <= m * n <= 10^4
- mat[i][j] is either 0 or 1.
- There is at least one 0 in mat.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
if (matrix.size() == 0)
return matrix;
int row = matrix.size();
int col = matrix[0].size();
vector<vector<int> > ans(row, vector<int> (col, INT_MAX));
queue<pair<int, int>> bfsQ;
for (int i = 0; i < row; i ++) {
for (int j = 0; j < col; j ++) {
if (matrix[i][j] == 0) {
ans[i][j] = 0;
bfsQ.push({i, j});
}
}
}
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
while (!bfsQ.empty()) {
pair<int, int> curr = bfsQ.front();
bfsQ.pop();
for (int i = 0; i < 4; i ++) {
int new_r = curr.first + dir[i][0];
int new_c = curr.second + dir[i][1];
if ((new_r >= 0) && (new_c >= 0) && (new_r < row) && (new_c < col)) {
if (ans[new_r][new_c] > ans[curr.first][curr.second] + 1) {
ans[new_r][new_c] = ans[curr.first][curr.second] + 1;
bfsQ.push({new_r, new_c});
}
}
}
}
return ans;
}
};