BFS C++ Iterative solution 168ms


  • 1
    R
    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            queue<pair<int, int>> q;
            for(int i = 0; i < rooms.size(); i++){
                for(int j = 0; j < rooms[0].size(); j++){
                    if(rooms[i][j] == 0){
                        q.emplace(i, j);
                    }
                }
            }
            while(!q.empty()){
                int size = q.size();
                for(int i = 0; i < size; i++){
                    int a = q.front().first;
                    int b = q.front().second;
                    int current = rooms[a][b];
                    q.pop();
                    if(a != 0){
                        if(rooms[a - 1][b] != -1){
                            if(rooms[a - 1][b] > current + 1){
                                rooms[a - 1][b] = current + 1;
                                q.emplace(a - 1, b);
                            }
                        }
                    }
                    if(b != 0){
                        if(rooms[a][b - 1] != -1){
                            if(rooms[a][b - 1] > current + 1){
                                rooms[a][b - 1] = current + 1;
                                q.emplace(a, b - 1);
                            }
                        }
                    }
                    if(a != rooms.size() - 1 && rooms[a + 1][b] != -1){
                        if(rooms[a + 1][b] > current + 1){
                            rooms[a + 1][b] = current + 1;
                            q.emplace(a + 1, b);
                        }
                    }
                    if(b != rooms[0].size() - 1 && rooms[a][b + 1] != -1){
                        if(rooms[a][b + 1] > current + 1){
                            rooms[a][b + 1] = current + 1;
                            q.emplace(a, b + 1);
                        }
                    }
                }
            }
        }
    };

Log in to reply
 

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