Beats 99% BFS C++ code


  • 0
    L
    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            int n = rooms.size();
            if(n==0) return;
            int m = rooms[0].size();
            if(m==0) return;
            vector<int> queue;
            for(int i = 0; i < n ; i++){
                for(int j = 0; j < m ; j++){
                    if(rooms[i][j] == 0)
                        queue.push_back(i*m+j);
                }
            }
            int l = 0;
            while(l<queue.size()){
                int x = queue[l]/m;
                int y = queue[l]%m;
                int step = rooms[x][y];
                if(x>0 && rooms[x-1][y]> step+1){
                    rooms[x-1][y] = step+1;
                    queue.push_back((x-1)*m+y);
                }
                if(y>0 && rooms[x][y-1]> step+1){
                    rooms[x][y-1] = step+1;
                    queue.push_back((x)*m+y-1);
                }
                if(x+1<n && rooms[x+1][y]> step+1){
                    rooms[x+1][y] = step+1;
                    queue.push_back((x+1)*m+y);
                }
                if(y+1<m && rooms[x][y+1]> step+1){
                    rooms[x][y+1] = step+1;
                    queue.push_back((x)*m+y+1);
                }
                l++;
            }
        }
    };
    

Log in to reply
 

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