You are given a

m x n2D grid initialized with these three possible values.

`-1`

– A wall or an obstacle.`0`

– A gate.`INF`

– Infinity means an empty room. We use the value`2`

to represent^{31}- 1 = 2147483647`INF`

as you may assume that the distance to a gate is less than`2147483647`

.Fill each empty room with the distance to its

nearestgate. 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 INFAfter 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[0].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.

- Start from gates, push gates in queue, Set distance as 0. Set lastNodeinLevel to q.back()
- while q is not empty:
- push legal neighbors of q.front() in queue and hash map. legal is defined as follows:
- is not out of boundary
- is not a wall (-1)
- does not ever existed in queue.

- set map[q.front().x][q.front().y] to distance
- if q.front() equal to lastNodeinLevel:
- distance++
- lastNodeinLevel = q.back() (if q is not empty yet)

- q.pop()

- push legal neighbors of q.front() in queue and hash map. legal is defined as follows:

//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[0].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[0].size(); j++){ if(rooms[i][j] == 0){ pair<int, int> nn = pair<int, int>(i, j); q.push(nn); map[i * rooms[0].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[][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; for(int i = 0; i < 4; i++){ int x = node.first + direct[i][0]; int y = node.second + direct[i][1]; if(x < 0 || y < 0 || x >= rooms.size() || y >= rooms[0].size()){ //out of boundary continue; } pair<int, int> nn = pair<int, int>(x, y); if(map.find(x * rooms[0].size() + y) != map.end()){ continue; } if(rooms[x][y] == -1){ continue; } q.push(nn); map[x * rooms[0].size() + y] = 1; } //already in map //is -1 } };