LeetCode 286: Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

 3  -1   0   1
 2   2   1  -1
 1  -1   2  -1
 0  -1   3   4

Solution C++

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

#define INF 100


void push_to_queue(vector<vector<int>>& rooms, queue<pair<int, int>>& q, int x, int y, int d){
    if(x >= 0 && x < rooms.size() && y >= 0 && y < rooms[0].size() && rooms[x][y] > d){
       q.push({x, y});
       rooms[x][y] = d;
    }
}

void bfs(vector<vector<int>>& rooms, int i, int j, int dist){
    queue<pair<int, int>> gates;
    gates.push({i, j});
    while(!gates.empty()){
       int count = gates.size();
       for(int _x = 0; _x < count; ++_x){
           pair<int, int> pos = gates.front();
           gates.pop();
           int x = pos.first;
           int y = pos.second;
           push_to_queue(rooms, gates, x, y+1, dist+1);
           push_to_queue(rooms, gates, x, y-1, dist+1);
           push_to_queue(rooms, gates, x+1, y, dist+1);
           push_to_queue(rooms, gates, x-1, y, dist+1);
       }
       dist++;
    }
}

void wallsAndGates(vector<vector<int>>& rooms) {
    for(int i = 0; i < rooms.size(); ++i){
       for(int j = 0; j < rooms[0].size(); ++j){
          if(!rooms[i][j])
             bfs(rooms, i, j, 0);
       }
    }
}

void print_rooms(vector<vector<int>> rooms){
    for(int i = 0; i < rooms.size(); ++i){
       for(int j = 0; j < rooms[0].size(); ++j){
           cout << rooms[i][j] << "\t";
       }
       cout << "\n";
    }
    cout << "-------------------\n";
}

int main() {
    vector<vector<int>> rooms = {
           {INF, -1, 0, INF},
           {INF, INF, INF, -1},
           {INF, -1, INF, -1},
           {0, -1, INF, INF}
    };
    print_rooms(rooms);
    wallsAndGates(rooms);
    print_rooms(rooms);
 
    return 0;
}