1179HardArrayBinary SearchBreadth-First SearchMatrix

Waiting Out the Creeping Slurry

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 quarry floor is laid out as m rows of n panels. panels[i][j] reads 0 for a firm panel, 1 for a panel already under slurry, and 2 for a pillar. You stand on the ramp at panels[0][0] and want to reach the shed at panels[m - 1][n - 1], and both of those are firm.

Time passes in whole minutes, and each minute of the walk holds two things in this order:

you step onto a panel sharing a side with the one you are on, and it must be firm and not yet under slurry;
the slurry then creeps onto every firm panel sharing a side with a panel already under it.

Pillars stop the slurry just as they stop you. If the slurry creeps onto the panel you are standing on, it has you. Stepping onto the shed ends the walk, so slurry creeping onto the shed during that same minute does not.

Before setting off you may linger on the ramp for a whole number of minutes, and the slurry creeps during every one of them. Once you set off you step every minute until you are on the shed.

Return the largest number of minutes you can linger and still reach the shed. Return 10^9 if you can linger for any number of minutes whatsoever, and -1 if you cannot reach the shed even by setting off at once.

Examples

Example 1

Input: panels = [[0, 0, 0, 1], [0, 2, 2, 2], [0, 0, 0, 0], [0, 0, 0, 0]]
Output: 2

The pillars leave one way down off the top row, so the walk to the shed is six steps and the slurry, starting at the far end of the top row, needs nine minutes to follow it there. Lingering three would land you on the shed as the slurry arrives, which is allowed, but it would also put the slurry on the panel before the shed while you were still standing on it. Lingering two keeps you a minute clear the whole way.

Example 2

Input: panels = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: -1

The slurry sits one panel from the shed and covers it after two minutes, while the shortest way around the wet middle panel takes four steps. The slurry is there first even if you leave at once.

Example 3

Input: panels = [[0, 0, 0, 0, 0], [0, 0, 2, 0, 0], [0, 2, 1, 2, 0], [0, 0, 2, 0, 0], [0, 0, 0, 0, 0]]
Output: 1000000000

Pillars hem the one wet panel in on all four sides, so the slurry never moves. Nothing on the way to the shed is ever wet, so the lingering has no ceiling.

Constraints

m == panels.length
n == panels[i].length
2 <= panels.length <= 300
2 <= panels[i].length <= 300
4 <= m * n <= 2 * 10^4
0 <= panels[i][j] <= 2
panels[0][0] == panels[m - 1][n - 1] == 0

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 maximum_minutes(panels: list[list[int]]) -> int:

Java

public int maximumMinutes(int[][] panels)

The intended approach

Time O(m * n) for the two sweeps.Space O(m * n) for the two tables of minutes.

Two sweeps of the floor answer everything. A breadth-first sweep out of every panel that starts under slurry gives `wet[i][j]`, the minute the slurry arrives there; a second sweep out of the ramp gives `walk[i][j]`, the earliest minute you could be standing there. Both sweeps step onto firm panels only, so pillars are missing from each of them. If the shed never picks up a walk time, nothing helps and the answer is `-1`. If the shed never picks up a wet time, then every panel of a route to it sits in the same pillar-free pocket as the shed and no slurry is in that pocket, so the lingering is unbounded and the answer is `10^9`. Otherwise weigh the two sweeps against each other: `slack[i][j] = wet[i][j] - walk[i][j]`. Along any shortest route out of the ramp the slack never rises, because one more step adds exactly one to the walk time while the slurry needs at most one extra minute to carry on to the next panel. So the shed's slack is the smallest slack on any shortest route to it. Call it `s`. Lingering `w` puts you on the shed at minute `w + walk`, which the slurry must not have beaten, so `w` can never exceed `s`. Lingering `s - 1` always works: every panel of a shortest route has slack `s` or more, which leaves you strictly ahead of the slurry the whole way. Lingering the full `s` works only when some shortest route reaches the shed from a panel whose slack is strictly above `s`, since a tie is forgiven on the shed alone. That panel is one of the two beside the shed, and because slack never rises along a route, one of those two clearing `s` drags the rest of the route clear with it. Those two panels are therefore the whole test. One of them whose walk time is not one below the shed's cannot pass it in any case, since its slack works out to `s` or less.

Pythonentry point: maximum_minutes

def maximum_minutes(panels):
    from collections import deque
    rows = len(panels)
    cols = len(panels[0])

    def sweep(sources):
        when = [[-1] * cols for _ in range(rows)]
        queue = deque()
        for r, c in sources:
            when[r][c] = 0
            queue.append((r, c))
        while queue:
            r, c = queue.popleft()
            step = when[r][c] + 1
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and when[nr][nc] < 0 and panels[nr][nc] == 0:
                    when[nr][nc] = step
                    queue.append((nr, nc))
        return when

    wet = sweep([(r, c) for r in range(rows) for c in range(cols) if panels[r][c] == 1])
    walk = sweep([(0, 0)])
    er = rows - 1
    ec = cols - 1
    if walk[er][ec] < 0:
        return -1
    if wet[er][ec] < 0:
        return 10 ** 9
    slack = wet[er][ec] - walk[er][ec]
    if slack < 0:
        return -1
    for r, c in ((er - 1, ec), (er, ec - 1)):
        if walk[r][c] >= 0 and wet[r][c] - walk[r][c] > slack:
            return slack
    return slack - 1 if slack > 0 else -1

The obvious version

Try each linger in turn and play the minutes out. Hold the wet panels in one set and every panel you could be standing on in another. Each minute, step the position set onto every firm panel that is not yet wet, calling it a success the moment the shed turns up among them, then creep the slurry outward by scanning the wet set. The positions can be carried as a plain set because the slurry's timetable does not depend on where you walked. Lingering longer never helps, since the wet set only ever grows, so the scan stops at the first linger that fails. A linger past `m * n + 4` can only come off when the slurry never reaches your route at all, which is the `10^9` case.

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_maximum_minutes(panels):
    rows = len(panels)
    cols = len(panels[0])
    shed = (rows - 1, cols - 1)
    cap = rows * cols + 4
    limit = 2 * rows * cols + cap + 4

    def steps(r, c):
        out = []
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and panels[nr][nc] == 0:
                out.append((nr, nc))
        return out

    def escapes(linger):
        wet = set()
        for r in range(rows):
            for c in range(cols):
                if panels[r][c] == 1:
                    wet.add((r, c))

        def creep():
            fresh = []
            for r, c in wet:
                for spot in steps(r, c):
                    if spot not in wet:
                        fresh.append(spot)
            wet.update(fresh)

        for _ in range(linger):
            creep()
            if (0, 0) in wet:
                return False
        here = {(0, 0)}
        for _ in range(limit):
            nxt = set()
            for r, c in here:
                for spot in steps(r, c):
                    if spot in wet:
                        continue
                    if spot == shed:
                        return True
                    nxt.add(spot)
            if not nxt:
                return False
            creep()
            here = set()
            for spot in nxt:
                if spot not in wet:
                    here.add(spot)
            if not here:
                return False
        return False

    best = -1
    for linger in range(cap + 1):
        if not escapes(linger):
            break
        best = linger
    if best == cap:
        return 10 ** 9
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 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