0532MediumArrayDepth-First SearchBreadth-First SearchMatrix

Planking Between Two Ice Floes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_planks(chart: list[list[int]]) -> int:

Java

public int minPlanks(int[][] chart)

The intended approach

Time O(n^2): every cell enters the flood or a ring at most once.Space O(n^2) for the reached marks and the ring being expanded.

Find any ice cell and flood its whole floe with an explicit stack, marking every cell of it as reached. Then grow outward from all of those cells at once, taking one ring of unreached cells per round and counting the rounds; a cell already reached is never queued twice, so each round is exactly the set of cells that one more plank puts within reach. The moment a ring touches an ice cell that was not part of the first floe, the count of full rounds so far is the number of planks used to get there.

Pythonentry point: min_planks

def min_planks(chart):
    # O(n^2): flood one floe with an explicit stack, then spread outward from
    # every one of its cells at once, one ring of water per round.
    n = len(chart)
    start = None
    for r in range(n):
        for c in range(n):
            if chart[r][c] == 1:
                start = (r, c)
                break
        if start:
            break
    seen = [[False] * n for _ in range(n)]
    stack = [start]
    seen[start[0]][start[1]] = True
    frontier = []
    while stack:
        r, c = stack.pop()
        frontier.append((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and chart[nr][nc] == 1:
                seen[nr][nc] = True
                stack.append((nr, nc))
    laid = 0
    while frontier:
        nxt = []
        for r, c in frontier:
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
                    if chart[nr][nc] == 1:
                        return laid
                    seen[nr][nc] = True
                    nxt.append((nr, nc))
        frontier = nxt
        laid += 1
    return laid

The obvious version

Label the ice cells into floes with a union-find over edge-sharing pairs, then take every cell of the first floe against every cell of the second and keep the smallest count of cells strictly between them along a staircase, which is one less than their row-plus-column separation.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_planks(chart):
    n = len(chart)
    par = list(range(n * n))

    def find(x):
        while par[x] != x:
            par[x] = par[par[x]]
            x = par[x]
        return x

    def join(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            par[ra] = rb

    for r in range(n):
        for c in range(n):
            if chart[r][c] == 1:
                if r + 1 < n and chart[r + 1][c] == 1:
                    join(r * n + c, (r + 1) * n + c)
                if c + 1 < n and chart[r][c + 1] == 1:
                    join(r * n + c, r * n + c + 1)
    groups = {}
    for r in range(n):
        for c in range(n):
            if chart[r][c] == 1:
                groups.setdefault(find(r * n + c), []).append((r, c))
    keys = list(groups.keys())
    here = groups[keys[0]]
    there = groups[keys[1]]
    best = None
    for r1, c1 in here:
        for r2, c2 in there:
            gap = abs(r1 - r2) + abs(c1 - c2) - 1
            if best is None or gap < best:
                best = gap
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in