Leetcode 286. Walls and Gates [Medium]

Problem:

source: walls-and-gates

Identify problem

Given a 2d grid each filled with either -1(wall), 0(gate),or INF(empty room), question asked us to fill in all the empty rooms with shortest distance to the gate.

Approaches

1. We could use dfs for individual indicies. For each room, we could consecutively look for rooms that are adjacent to current room of investigation and find whether we have reached to gate. This solution however takes $O((row of rooms * colume of rooms)^2)$ time complexity

2. Use bfs starting from all the gates simultaneously. Using queues to track all the visited rooms, we would be able to fill up the empty rooms with distance in $O($row of rooms * colume of rooms)$)$ time complexity.

Code

class Solution {
public:
    
    
    //from: https://stackoverflow.com/questions/15160889/how-can-i-make-an-unordered-set-of-pairs-of-integers-in-c
    struct IntPairHash {
      std::size_t operator()(const std::pair<uint32_t, uint32_t> &p) const {
        assert(sizeof(std::size_t)>=8);  //Ensure that std::size_t, the type of the hash, is large enough
        //Shift first integer over to make room for the second integer. The two are
        //then packed side by side.
        return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
      }
    };
    
    //Actual Code
    void wallsAndGates(vector<vector<int>>& rooms) {
        int num_row = rooms.size(); 
        int num_col = rooms[0].size();
        
        unordered_set<pair<int,int>, IntPairHash> visited;
        queue<pair<int, int>> q;
        
        //put all the gate inside q and mark them as visited
        for(int r=0; r<num_row; ++r)
        {
            for(int c=0; c<num_col; ++c)
            {
                if(rooms[r][c] == 0)
                {
                    visited.insert(make_pair(r,c));
                    q.push(make_pair(r,c));
                }
            }
        }
        
        //dfs code
        int distance = 0; 
        while(!q.empty())
        {
            int cur_level_size = q.size(); // Note q size changes so we can not directly put this inside for loop condition.
            
            for(int i=0; i<cur_level_size; ++i)
            {
                auto [row, col] = q.front();
                q.pop();
                
                rooms[row][col] = distance;
                
                for(int k=0; k<4; k++)
                {
                    int n_row = row + dr[k];
                    int n_col = col + dc[k];
                    
                    if(0<=n_row && n_row<num_row &&
                       0<=n_col && n_col<num_col &&
                       visited.find(make_pair(n_row, n_col)) == visited.end() &&
                       rooms[n_row][n_col] == std::numeric_limits<int>::max())
                    {
                        visited.insert(make_pair(n_row, n_col));
                        q.push(make_pair(n_row, n_col));
                    }
                }
            }
            distance++;
        }
    }
    
private:
    int dr[4] = {0, 0, 1, -1};
    int dc[4] = {1, -1, 0, 0};
};

Notes

1. We cannot use pair within unordered_set, since standard library hash does not support it.