My bfs c++ solution


  • 0
    A

    Straightforward bfs approach, a little lengthy but the 4 if blocks are just copy and paste

    void wallsAndGates(vector<vector<int>>& rooms) {
        queue<int> points;
        if(rooms.empty()) return;
        int m = rooms.size(), n = rooms.begin()->size();
        for(int i = 0; i<m; ++i){
            for(int j =0; j<n; ++j){
                if(rooms[i][j]==0) points.push(i*n+j);
            }
        }
        int lvl = 0;
        while(!points.empty()){
            int k=points.size();
            ++lvl;
            for(int i =0; i<k; ++i){
                int pos0 = points.front();
                int pos = points.front()-n;
                if(pos>=0 && pos<m*n && rooms[pos/n][pos%n]==INT_MAX){
                    rooms[pos/n][pos%n]=lvl;
                    points.push(pos);
                }
                pos = points.front()+n;
                if(pos>=0 && pos<m*n && rooms[pos/n][pos%n]==INT_MAX){
                    rooms[pos/n][pos%n]=lvl;
                    points.push(pos);
                }
                pos = points.front()-1;
                if(pos%n!=n-1){//when pos is first of the line, last pos is not adjacent   
                    if(pos>=0 && pos<m*n && rooms[pos/n][pos%n]==INT_MAX){
                        rooms[pos/n][pos%n]=lvl;
                        points.push(pos);
                    }
                    
                }
                pos = points.front()+1;
                if(pos%n !=0){
                    if(pos>=0 && pos<m*n && rooms[pos/n][pos%n]==INT_MAX){
                        rooms[pos/n][pos%n]=lvl;
                        points.push(pos);
                    }
                    
                }
                
                points.pop();
            }
        }
    }

Log in to reply
 

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