Easy Understand C++ Solution Using BFS


  • 0
    H
    class Solution {
    public: void wallsAndGates(vector<vector<int>>& rooms) {
        queue<pair<int,int>> myq;
    
        for(int i = 0;i<rooms.size();i++){
            for(int j = 0; j< rooms[0].size();j++){
                if(rooms[i][j] == 0){
                    pair <int,int> newpair;
                    newpair.first = i;
                    newpair.second = j;
                    myq.push(newpair);
                }
            }
        }
        while(!myq.empty()){
            int x = myq.front().first;
            int y = myq.front().second;
            if(isValid(rooms,x+1,y)){
                rooms[x+1][y] = rooms[x][y]+1;
                pair <int,int> newpair;
                newpair.first = x+1;
                newpair.second = y;
                myq.push(newpair);
                
                
            }
            if(isValid(rooms,x-1,y)){
                rooms[x-1][y] = rooms[x][y]+1;
                pair <int,int> newpair;
                newpair.first = x-1;
                newpair.second = y;
                myq.push(newpair);
                
            }
            if(isValid(rooms,x,y+1)){
                rooms[x][y+1] = rooms[x][y]+1;
                pair <int,int> newpair;
                newpair.first = x;
                newpair.second = y+1;
                myq.push(newpair);
                
            }
            if(isValid(rooms,x,y-1)){
                rooms[x][y-1] = rooms[x][y]+1;
                pair <int,int> newpair;
                newpair.first = x;
                newpair.second = y-1;
                myq.push(newpair);
                
            }
            myq.pop();
        
        }
        
    }
    bool isValid(vector<vector<int>>& rooms,int x,int y){
        int INF = 2147483647;
        int row = rooms.size();
        int col = rooms[0].size();
        if(x<0 || x>= row){
            return false;
        }
        if(y<0 || y>= col){
            return false;
        }
        if(rooms[x][y] == -1){
            return false;
        }
        if(rooms[x][y] == INF){
            return true;
        }
        return false;
    }};

Log in to reply
 

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