Show problems as
Classic problem #317HardArrayBreadth-First SearchMatrix

Shortest Distance from All Buildings

Real-world version: Siting the Campus Bike Rack
Tracked in this browser only
Read Shortest Distance from All Buildings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A campus plan arrives as grid. Each cell holds one of three codes:

  • 0 is paved walkway, which people may stand on and walk across.
  • 1 is a lecture hall.
  • 2 is a fenced-off works area, which nobody may enter.

A bike rack has to go on one walkway cell. From a walkway cell a person may step to the cell directly above, below, left or right. A route from the chosen cell to a lecture hall is a chain of such steps that begins on the chosen cell, ends on that hall, and whose every other cell is walkway; the length of the route is the number of steps it contains. The reach of a walkway cell is the sum, over all lecture halls, of the length of the shortest route from that cell to that hall.

Return the smallest reach over all walkway cells from which every lecture hall has at least one route. If no walkway cell can route to every hall, return -1.

Examples

Example 1

Input
grid = [[0, 0, 1, 0], [0, 2, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1]]
Output
6

Put the rack on the walkway cell at row 2 column 2. Its shortest route to the hall at row 0 column 2 is two steps, to the hall at row 2 column 0 is two steps, and to the hall at row 3 column 3 is two steps, so its reach is 6, and no walkway cell has a smaller reach.

Example 2

Input
grid = [[0, 1, 0, 0], [2, 0, 2, 0], [0, 0, 0, 1]]
Output
4

The cell at row 0 column 2 is one step from the hall at row 0 column 1 and three steps from the hall at row 2 column 3, a reach of 4, which is the smallest reach on this plan.

Example 3

Input
grid = [[1, 0, 0], [2, 1, 2], [1, 0, 0]]
Output
-1

The works areas at row 1 column 0 and row 1 column 2 leave the two walkway cells of row 0 and the two walkway cells of row 2 with no chain of walkway steps between them, so no single cell has a route to all three halls and the answer is -1.

Constraints

  • rows == grid.length
  • cols == grid[i].length
  • 1 <= rows, cols <= 50
  • grid[i][j] is 0, 1, or 2.
  • grid holds at least one lecture hall.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shortest_distance(grid: list[list[int]]) -> int:
Java
public int shortestDistance(int[][] grid)

More on the same topics