Leetcode – Wall and Gates

Tags: ,

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:

After running your function, the 2D grid should be:

Analysis

The standard solution to search the shortest path in a unweighted graph is to use the bread first search algorithm (BFS).

We can start from each gate,  and use BFS to calculate the shortest length for each empty room that can be reachable from the gate.  Since a room may be reachable from different gates, when the current shortest path from a gate is less than the shortest path from a previous gate, we update the value. 

Please Note:

  1. To prevent duplicated visits, we should not visit the gates in the path, as each gate will be traversed as the root. 
  2. In bread first search, we need to track the visited node to prevent unnecessary duplicated visits. 
  3. Since a room can not be reachable through a wall, the wall node should not put into the queue. 

The following is the Java Implementation:

The output:

3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

Please leave a comment if you have any questions or want to share a better solution.

Reference:

https://segmentfault.com/a/1190000003906674

https://discuss.leetcode.com/category/358/walls-and-gates