Walls And Gates

TLE first. Forgot to group states.

Each cell have three states

1) wall : -1

2) gate : 0

3) empty room: inf. Target: Fill each room with nearest gate.

Code Description.

Step 1 : group all gates in one queue, and do bfs at same time. Step 2: all cells in queue are at same level, later genearted must be larger than current cells.

Time : O(mn) Space: O(mn)

Explanation about global init:

1. shortest path to any of the walls == shortest path to global init.
2. all cells cost later generated will be larger than previous cells.