C++ Multi-end BFS clean and easy to understand


  • 0
    B
    class Solution {
        int height;
        int width;
        struct POINT {
            int x;
            int y;
        };
        queue<POINT> q;
        
        void bfs(vector<vector<int>>& rooms)
        {
            int dist = 0;
            while(!q.empty())
            {
                int size = q.size();
                for(int i=0;i<size;i++)
                {
                    POINT point = q.front();q.pop();
                    int& y=point.y;
                    int& x=point.x;
    
                    if(y<0 || y>height-1 || x<0 || x>width-1 || rooms[y][x]==-1 || dist > rooms[y][x] ) continue; //dist > rooms[y][x]!!
                    rooms[y][x] = dist;
                    q.push({x+1,y});
                    q.push({x-1,y});
                    q.push({x,y+1});
                    q.push({x,y-1});
                }
                dist++;
            }
        }
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            height = rooms.size();
            if(height<=0) return;
            width = rooms[0].size();
            for(int y=0;y<height;y++)
            {
                for(int x=0;x<width;x++)
                {
                    if(rooms[y][x]==0) {
                        q.push(POINT{x,y});
                    }
                }
            }
            bfs(rooms);
        }
    };
    

Log in to reply
 

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