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;
    }
};




Related Posts

Average Of Levels In Binary Tree Problem

LeetCode 637. Given the root of a binary tree, return...

Zuma Game Problem

LeetCode 488. You are playing a variation of the game...

Trapping Rain Water II Problem

LeetCode 407. Given an m x n integer matrix heightMap...

Pacific Atlantic Water Flow Problem

LeetCode 417. There is an m x n rectangular island...

N-Ary Tree Level Order Traversal Problem

LeetCode 429. Given an n-ary tree, return the level order...

Minimum Genetic Mutation Problem

LeetCode 433. A gene string can be represented by an...