C++ BFS with queue


  • 0
    B
    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            int row = matrix.size(), col = matrix[0].size();
            vector<vector<int>>ans(row, vector<int>(col,0));
            queue<pair<int,int>>bfs;
            for(int i = 0; i < row; i++)
                for(int j = 0; j < col; j++)
                    if(matrix[i][j] == 0) bfs.push(make_pair(i,j));
            while(!bfs.empty())
            {
                auto head = bfs.front();
                bfs.pop();
                if(head.first > 0 && ans[head.first-1][head.second] == 0 && matrix[head.first-1][head.second] == 1)
                {
                    ans[head.first-1][head.second] = ans[head.first][head.second] + 1;
                    bfs.push(make_pair(head.first-1, head.second));
                }
                if(head.second > 0 && ans[head.first][head.second-1] == 0 && matrix[head.first][head.second-1] == 1)
                {
                    ans[head.first][head.second-1] = ans[head.first][head.second] + 1;
                    bfs.push(make_pair(head.first, head.second-1));
                }
                if(head.first + 1 < row && ans[head.first+1][head.second] == 0 && matrix[head.first+1][head.second] == 1)
                {
                    ans[head.first+1][head.second] = ans[head.first][head.second] + 1;
                    bfs.push(make_pair(head.first+1, head.second));
                }
                if(head.second+1 < col && ans[head.first][head.second+1] == 0 && matrix[head.first][head.second+1] == 1)
                {
                    ans[head.first][head.second+1] = ans[head.first][head.second] + 1;
                    bfs.push(make_pair(head.first,head.second+1));
                }
            }
            return ans;
        }
    };

Log in to reply
 

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