- Walls and Gates
1. Walls and Gates
O(MN): BFS + starts from the gates
寻找最短路径。
思维要逆向着来。虽然要mark的是从空房间到gate的路径，但是明显从，gate反向倒到空房间算distance要方便多了。
这道题不可以用dfs，会run time error，而且每个地点要visit好几次。所以用bfs，保证每个地点只visit一次。
我们不从 INF 的角度开始，而是反过来，从 0 开始往回找，沿路只添加看到的 INF; 由于是 BFS，从gate出发，每次看到某个房间的时候就是最短距离，因为只visit 一次。这样我们有 O(mn) 个可能的起点和位置要搜，然而每个位置只会进入队列一次，所以时间和空间复杂度都是 O(mn).