problem286

README

< Previous 　　　　　　　　　　　　　　　　 Next >

286. Walls and Gates (Medium)

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.

Example: 

Given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

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

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

Related Topics

[Breadth-first Search]

Similar Questions

1. Surrounded Regions (Medium)
2. Number of Islands (Medium)
3. Shortest Distance from All Buildings (Hard)
4. Robot Room Cleaner (Hard)
5. Rotting Oranges (Medium)