A town is divided into a rectangular grid of neighborhoods. Some neighborhoods contain fire stations.

In one minute, a fire truck can move to any horizontally, vertically, or diagonally neighboring cell. Therefore, the travel time between neighborhoods (firstRow, firstColumn) and (secondRow, secondColumn) is:

max(abs(firstRow - secondRow), abs(firstColumn - secondColumn))

Grid Values

• 1 represents a neighborhood with a fire station.
• 0 represents a neighborhood without a fire station.

Response Time

The response time for a neighborhood is its travel time from the nearest fire station. The town's response time is the largest response time among all neighborhoods.

The town may build one additional fire station by changing at most one 0 to 1. Return the smallest possible response time for the town.

Function

minimumFireResponseTime

int minimumFireResponseTime(List<List<Integer>> townMap)

• townMap represents the neighborhoods of the town.
• Return the minimum possible response time.

Rules

• Rows and columns are zero-indexed.
• Existing fire stations cannot be removed.
• The new fire station may be built only in a neighborhood containing 0.
• Building a new fire station is optional when the current placement is already optimal.
• If the grid has no fire station, one new fire station must be built.
• If every neighborhood has a fire station, return 0.

Constraints

• 1 ≤ townMap.size() ≤ 500
• 1 ≤ townMap.get(i).size() ≤ 500
• Every row contains the same number of neighborhoods.
• townMap.get(i).get(j) is either 0 or 1.

Example 1

minimumFireResponseTime( townMap = List.of( List.of(1, 0, 0), List.of(0, 0, 0), List.of(0, 0, 0) ))

Output: 1

Build the new fire station at neighborhood (1, 1). Every neighborhood is then at most one minute from a fire station.

Example 2

minimumFireResponseTime( townMap = List.of( List.of(0, 0, 0, 0, 0), List.of(0, 0, 0, 0, 0), List.of(0, 0, 0, 0, 0), List.of(0, 0, 0, 0, 0), List.of(0, 0, 0, 0, 0) ))

Output: 2

Build a fire station at neighborhood (2, 2). The farthest neighborhoods are two minutes away.

Example 3

minimumFireResponseTime( townMap = List.of( List.of(1, 1, 1), List.of(1, 1, 1) ))

Output: 0

Every neighborhood already contains a fire station, so every response time is zero.