144ms C++ solution with BFS


  • 1
    A
    class Solution {
    public:
        void wallsAndGates(vector<vector<int>>& rooms) {
            
            queue<pair<int,int>> q;
            
            int rows = rooms.size();
            if (rows == 0)
                return;
            int cols = rooms[0].size();
            
            // Add the (i,j) coordinate of every gate to the queue
            for (int i=0; i<rows; ++i) {
                for (int j=0; j<cols; ++j) {
                    pair<int, int> p(i, j);
                    if (rooms[i][j]==0) {
                        q.push(p);
                    }
                }
            }
            array<int, 5> dir = {0, 1, 0, -1, 0};
            
            // Breadth first search
            while (!q.empty()) {
                pair<int,int> p = q.front();
                q.pop();
            
                // For every element in the queue, try to move in all four directions (east, north, west, south)
                for (int k=0; k<4; ++k) {
                    // Coordinates of the old position
                    int old_i = p.first;
                    int old_j = p.second;
                    
                    // Coordinates of the new position
                    int new_i = old_i+dir[k];
                    int new_j = old_j+dir[k+1];
                    
                    /** If the new position is still within the boundaries of rooms (the first four conditions of the if statement),
                        and if the new position corresponds to an empty room (rooms[new_i][new_j]==INT_MAX),
                        then update rooms[new_i][new_j] to be rooms[old_i][old_j]+1
                        (= distance of the old position to the nearest gate + 1).
                        Then add the coordinates of the new position to the queue.
                     */
                    if (new_i>=0 && new_i<rows && new_j>=0 && new_j<cols && rooms[new_i][new_j]==INT_MAX) {
                        rooms[new_i][new_j] = rooms[old_i][old_j]+1;
                        pair<int,int> p2(new_i, new_j);
                        q.push(p2);
                    }
                }
                
            }
        }
    };

Log in to reply
 

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