0542. 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.

Analysis

Using BFS to find the shortest path for each point

Compared to single-source BFS, we can regard each "0" as a source and run the search from each point. BFS will guarantee the shortest path, so we can return the search results immediately after each search.

1. Scan through all the "0"s and insert their coordinates into the search queue, and initialize a dist matrix with 0 at each of those coordinates and -1 (unvisited) everywhere else.
2. Run a standard multi-source BFS: pop a coordinate from the queue, and for each of its 4 neighbors that hasn't been visited yet (dist == -1), set its distance to the current cell's distance plus one and push it into the queue.

3. Keep expanding level by level until the queue is empty. Since every "0" starts the search at distance 0 simultaneously, the first time we reach a cell is guaranteed to be via the shortest path, so dist ends up holding the answer for every cell.

4. Time: $O(mn)$ since every cell is pushed onto and popped from the queue at most once.

5. Space: $O(mn)$ for the dist matrix and the queue.

Code

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
        int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!q.empty()) {
            int x, y;
            tie(x, y) = q.front();
            q.pop();
            for (auto& d : dir) {
                int dx = x + d[0], dy = y + d[1];
                if (dx < 0 || dx >= m || dy < 0 || dy >= n || dist[dx][dy] != -1)
                    continue;
                dist[dx][dy] = dist[x][y] + 1;
                q.push({dx, dy});
            }
        }
        return dist;
    }
};