Hard · Graphs

Shortest Distance from All Buildings

Given an m × n grid where 0 is empty land, 1 is a building and 2 is an obstacle, return the smallest total number of 4-directional steps through empty land from one empty cell to every building, or −1 if no empty cell can reach all buildings.

Examples

Example 1

{
  "grid": [
    [1, 0, 2, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0]
  ]
}

Output: min total = 7

Example 2

{
  "grid": [
    [1, 0, 0],
    [0, 0, 0],
    [0, 0, 1]
  ]
}

Output: min total = 4

Rebuild it in the studio

Open every published interview problem, solution, scene, and memory room free, with no account.