Show problems as
Classic problem #934MediumArrayDepth-First SearchBreadth-First SearchMatrix

Shortest Bridge

Real-world version: Planking Between Two Ice Floes
Tracked in this browser only
Read Shortest Bridge on LeetCode(opens in a new tab)

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

A survey of a frozen bay comes back as chart, a square grid where 1 marks a cell of solid ice and 0 marks open water. Two ice cells belong to the same floe when they share an edge; touching only at a corner does not join them. The chart shows exactly two floes.

A crew joins the floes by laying planks. Laying a plank fills one water cell and turns it into part of the walkable surface, again joined to whatever it shares an edge with.

Return the smallest number of water cells the crew has to plank so that the two floes end up on one connected walkable surface.

Examples

Example 1

Input
chart = [[1, 0], [0, 1]]
Output
1

The two ice cells touch only at a corner, so they are separate floes. Planking the water cell at row 1, column 0 gives a surface where all three cells share edges.

Example 2

Input
chart = [[1, 1, 1], [0, 0, 0], [1, 1, 1]]
Output
1

Planking the water cell at row 1, column 0 puts it edge to edge with the ice above and the ice below, joining the two floes.

Example 3

Input
chart = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0]]
Output
4

Planking the cells at row 0 column 1, row 0 column 2, row 0 column 3 and row 1 column 3 leaves a chain of edge-sharing cells running from one floe to the other, using 4 planks.

Constraints

  • n == chart.length == chart[i].length
  • 2 <= n <= 100
  • chart[i][j] is 0 or 1.
  • The chart holds exactly two floes.

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 min_planks(chart: list[list[int]]) -> int:
Java
public int minPlanks(int[][] chart)

More on the same topics