C++ BFS solution sharing


  • 0

    This problem is similar to https://leetcode.com/problems/walls-and-gates/#/description

    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            vector<vector<int>> ans;
            int rows = matrix.size(); if (!rows) return ans;
            int cols = matrix[0].size(); 
            ans = vector<vector<int>>(rows, vector<int>(cols, INT_MAX));
            queue<pair<int, int>> q; queue<int> dist;
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    if (matrix[i][j] == 0) {
                        ans[i][j] = 0;
                        q.push({i, j});
                        matrix[i][j] = -1;
                        dist.push(0);
                    }
                }
            }
            
            int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
            while (!q.empty()) {
                auto pos = q.front(); q.pop();
                auto d = dist.front(); dist.pop();
                for (int i = 0; i < 4; ++i) {
                    int xx = pos.first + dx[i], yy = pos.second + dy[i];
                    if (xx < 0 || yy < 0 || xx >= rows || yy >= cols) continue;
                    if (matrix[xx][yy] == -1) continue;
                    matrix[xx][yy] = -1;
                    dist.push(d + 1);
                    q.push({xx, yy});
                    ans[xx][yy] = std::min(ans[xx][yy], d + 1);
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.