C++ iterative BFS flood using queue


  • 0
    B
    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            if(rooms.empty() || rooms[0].empty()) return;
            deque<pair<int,int>>dq;
            for(int i = 0; i < rooms.size(); i++)
                for(int j = 0; j < rooms[0].size(); j++)
                    if(rooms[i][j] == 0) dq.push_back(make_pair(i,j));
            while(!dq.empty())
            {
                int r = dq.front().first;
                int c = dq.front().second;
                dq.pop_front();
                if(r>0 && rooms[r-1][c] == INT_MAX)
                {
                    rooms[r-1][c] = rooms[r][c]+1;
                    dq.push_back(make_pair(r-1,c));
                }
                
                if(c>0 && rooms[r][c-1] == INT_MAX)
                {
                    rooms[r][c-1] = rooms[r][c]+1;
                    dq.push_back(make_pair(r,c-1));
                }
                
                if(r+1<rooms.size() && rooms[r+1][c] == INT_MAX)
                {
                    rooms[r+1][c] = rooms[r][c]+1;
                    dq.push_back(make_pair(r+1,c));
                }
                
                if(c+1 < rooms[0].size() && rooms[r][c+1] == INT_MAX)
                {
                    rooms[r][c+1] = rooms[r][c]+1;
                    dq.push_back(make_pair(r,c+1));
                }
            }
        }
    };

Log in to reply
 

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