# [leetcode] 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
```

A typical topological sort question. Interesting.

There are some tricky corners we should keep in mind.

First, always test q.empty() before you want to access a element in queue.

Second, pair<int, int> is not hashable, so you should store map<int, int> and write your simple hash function (i * rooms.size() + j in my case)

Third, use an index to indicate the last node of current level in the queue. It is like algorithm in level order traversal of a tree.

1. Start from gates, push gates in queue, Set distance as 0. Set lastNodeinLevel to q.back()
2. while q is not empty:
1. push legal neighbors of q.front() in queue and hash map. legal is defined as follows:
1. is not out of boundary
2. is not a wall (-1)
3. does not ever existed in queue.
2. set map[q.front().x][q.front().y] to distance
3. if q.front() equal to lastNodeinLevel:
1. distance++
2. lastNodeinLevel = q.back() (if q is not empty yet)
4. q.pop()
```//topological sort
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
//find all gates, and push the neighbors of gates in queue.(1. it's not in queue before, 2. it's not a -1)
if(rooms.size() == 0 || rooms.size() == 0) return ;
unordered_map<int, int> map;
queue<pair<int, int>> q;
pair<int, int> lastNodeinLevel;
int distance = 0;
for(int i = 0; i < rooms.size(); i++){
for(int j = 0; j < rooms.size(); j++){
if(rooms[i][j] == 0){
pair<int, int> nn = pair<int, int>(i, j);
q.push(nn);
map[i * rooms.size() + j] = 1;
}
}
}
if(q.empty()){//BUG HERE
return ;
}
lastNodeinLevel = q.back();
distance = 0;
while(!q.empty()){
pair<int, int> node = q.front();
q.pop();
rooms[node.first][node.second] = distance;
pushNeighborsInQueue(rooms, map, q, node);
if(node == lastNodeinLevel && !q.empty()){
lastNodeinLevel = q.back();
distance++;
}
}
}
void pushNeighborsInQueue(vector<vector<int>>& rooms, unordered_map<int, int>& map, queue<pair<int, int>>& q, pair<int, int>& node){
int direct[] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
for(int i = 0; i < 4; i++){
int x = node.first + direct[i];
int y = node.second + direct[i];
if(x < 0 || y < 0 || x >= rooms.size() || y >= rooms.size()){
//out of boundary
continue;
}
pair<int, int> nn = pair<int, int>(x, y);
if(map.find(x * rooms.size() + y) != map.end()){
continue;
}
if(rooms[x][y] == -1){
continue;
}
q.push(nn);
map[x * rooms.size() + y] = 1;
}