Walls and Gates


I'm failing to see how the 2nd solution works in a situation where a room has access to multiple gates. The solution only updates the distance if the cell value is EMPTY. But what if at a later point, we do bfs from a different gate which is closer to this cell value. Shouldn't we update that cell if it's distance is greater than from this new gate?


It will still work @ichuen because the BFS algorithm will make sure that when the empty room is discovered first, that means the distance is the shortest at that time.

Maybe this will help you to see how it works:
Add all the Gates (zeros) to the Queue, this is the first step, done prior to starting the BFS loop.
Now you start BFS from each of the found Gates, expanding outward. When you encounter a cell that has not been reached yet (you know this because it's value is INF) it will necessarily be one more than your current cell. If you reached it quicker via some other Gate it's value would have already been set (no longer INF) and thus your path is longer, so ignore it. As you find cells that you have not reached yet, after setting their value, add them to the Queue. Eventually the queue is empty and all the reachable cells have been treated.

I think it is still O(m * n) because
step 1: you iterate over all rows and columns giving mn operations each of O(1).
step 2: then you start at each gate and do 4 directions, adding in other cells until you have looked at every cell. The key here is that you will only look at each cell once during this process, so again you have O(mn) it doesn't matter how many initial gates you have you will still iterate over every cell once during this process.The result of these 2 steps is O(m*n). Number of gates doesn't matter because you are marking the cells completed as your process them to ensure you process each cell once regardless of what was in your initial queue of starting points.

Good job! The second solution is beautiful and definitely right. Because we use BFS in each GATE, each time we move one step and mark the shortest in one cell. As long as this cell is marked, we don't have to visit and remark it again. That's it. Scan the whole matrix one time. Time complexity definitely O(m * n).

I think what some folks are missing in this second solution is that each gate is not fully searched before moving on to a new gate. Each gate only looks at the areas within 1 space before we check the next gate. So each area within one space of the gates are checked for rooms and these rooms are marked, then added to the queue. Once all gates are checked, each new space is checked, and so forth. So, once a room gets hit, it has to be from the closest gate.