Walls and Gates / Zombie in Matrix
You are given an m
by n
grid of integers representing a map of a dungeon. In this map:
-1
represents a wall or an obstacle of some kind.0
represents a gate out of the dungeon.INF
represents empty space.
For this question, let INF
be 2^31 - 1 == 2147483647
, which is the max value of
the integer type in many programming languages.
Venturing into the dungeon is very dangerous, so you would like to know how close you are at
each point in the dungeon to the closest exit. Given the map of the dungeon, return the same map,
but for each empty space, that space is replaced by the number of steps it takes to reach
the closest exit. If a space cannot reach the exit, that space remains INF
.
Note that each step, you can move horizontally or vertically, but you cannot move pass a wall or an obstacle.
Input
dungeon_map
: a matrix of integer representing the dungeon map.
Output
A matrix of integer representing the dungeon map with the addition of distance to an exit for each empty space.
Examples
Example 1:
Input:
1dungeon_map = [ 2 [INF, -1, 0, INF], 3 [INF, INF, INF, -1], 4 [INF, -1, INF, -1], 5 [0, -1, INF, INF], 6]
Output: [ [3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4], ]
Explanation:
Constraints
1 <= n, m <= 500