c++ bfs solution


  • 0
    T
    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            
            int h = matrix.size(), w = matrix[0].size();
            
            auto dist = vector<vector<int>>(h, vector<int>(w, 0));
            queue<pair<int, int>> qid;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    if (matrix[i][j]) {
                        dist[i][j] = INT_MAX;
                    } else {
                        qid.emplace(i, j);
                    }
                }
            }
            vector<vector<int>> nei{{0,1},{0,-1},{1,0},{-1,0}};
            while (!qid.empty()) {
                int i = qid.front().first, j = qid.front().second;
                qid.pop();
                for (auto &p:nei) {
                    int ni = i+p[0], nj = j+p[1];
                    if (ni >= 0 && ni < h && nj >= 0 && nj < w && dist[ni][nj] > dist[i][j]+1) {
                        dist[ni][nj] = dist[i][j]+1;
                        qid.emplace(ni, nj);
                    }
                }
            }
            return dist;
        }
    };
    

Log in to reply
 

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