0271EasyArrayDepth-First SearchBreadth-First SearchMatrix

Recode the Contiguous Soil Block

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 field survey stores one soil code per plot in a rectangular grid. plots[r][c] is the code recorded for the plot in row r, column c.

A soil treatment is booked for the plot at row sr, column sc. From there it creeps into any plot that shares a full edge with a treated plot (above, below, left or right) and carries the same code as the booked plot, and it keeps creeping outward from every plot it reaches. Plots that meet only at a corner are never reached this way.

Every plot the treatment reaches takes the code code. Apply the change to the grid you were given and return that same grid. If code is already the booked plot's code, the grid comes back exactly as it arrived.

Examples

Example 1

Input: plots = [[7, 7, 2], [7, 2, 7], [2, 7, 7]], sr = 0, sc = 0, code = 4
Output: [[4, 4, 2], [4, 2, 7], [2, 7, 7]]

The booked plot carries code 7. The plot to its right and the plot below it also carry 7 and share an edge with it, so three plots take code 4. The 7s in the lower right meet that group only at a corner, so they keep their code.

Example 2

Input: plots = [[3, 3], [3, 3]], sr = 1, sc = 1, code = 3
Output: [[3, 3], [3, 3]]

The requested code is already the booked plot's code, so every plot the treatment reaches keeps the value it had.

Example 3

Input: plots = [[1, 2], [2, 1]], sr = 0, sc = 0, code = 2
Output: [[2, 2], [2, 1]]

The booked plot carries code 1 and neither plot sharing an edge with it carries 1, so only that one plot takes code 2. The 1 in the opposite corner is untouched.

Constraints

m == plots.length
n == plots[i].length
1 <= m, n <= 50
0 <= plots[i][j], code < 2^16
0 <= sr < m
0 <= sc < n

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 recode_soil_block(plots: list[list[int]], sr: int, sc: int, code: int) -> list[list[int]]:

Java

public int[][] recodeSoilBlock(int[][] plots, int sr, int sc, int code)

The intended approach

Time O(m * n)Space O(m * n) for the stack in the worst case

Read the booked plot's code first and return immediately when the requested code equals it, which also removes any risk of walking in circles. Otherwise push the booked plot onto an explicit stack and re-code it, then repeatedly pop a plot and push each of its four edge neighbours that still carries the original code, re-coding each one as it is pushed. Writing the new code at push time doubles as the visited marker, and the explicit stack keeps the walk off the interpreter's call stack.

Pythonentry point: recode_soil_block

def recode_soil_block(plots, sr, sc, code):
    # Depth-first spread driven by an explicit stack, so a block that covers all
    # 2500 plots of the largest allowed grid cannot overflow the call stack.
    # A plot is re-coded at the moment it is pushed, which is what keeps it from
    # entering the stack twice.
    # Time: O(m * n).  Space: O(m * n) for the stack in the worst case.
    original = plots[sr][sc]
    if original == code:
        return plots
    rows = len(plots)
    cols = len(plots[0])
    plots[sr][sc] = code
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        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 plots[nr][nc] == original:
                plots[nr][nc] = code
                stack.append((nr, nc))
    return plots

The obvious version

Mark the booked plot, then sweep the whole grid over and over, marking any unmarked plot that carries the original code and touches an already marked plot by an edge. Stop when a full sweep marks nothing new, then build the answer grid from the marks.

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_recode_soil_block(plots, sr, sc, code):
    rows = len(plots)
    cols = len(plots[0])
    original = plots[sr][sc]
    reached = [[False] * cols for _ in range(rows)]
    reached[sr][sc] = True
    changed = True
    while changed:
        changed = False
        for r in range(rows):
            for c in range(cols):
                if reached[r][c] or plots[r][c] != original:
                    continue
                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 reached[nr][nc]:
                        reached[r][c] = True
                        changed = True
                        break
    return [[code if reached[r][c] else plots[r][c] for c in range(cols)]
            for r in range(rows)]

How this problem was checked

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