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 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 any 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:

dungeon_map = [
  [INF, -1, 0, INF],
  [INF, INF, INF, -1],
  [INF, -1, INF, -1],
  [0, -1, INF, INF],
]

Output: [ [3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4], ]

Explanation:

Constraints

  • 1 <= n, m <= 500

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade