Show problems as
Classic problem #130MediumArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Surrounded Regions

Real-world version: Seal The Trapped Pockets
Tracked in this browser only
Read Surrounded Regions on LeetCode(opens in a new tab)

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

A gasket sheet is inspected cell by cell and handed to you as sheet, a grid of rows rows and cols columns. Every cell carries one character: "X" for solid material, "O" for an open channel.

Two open cells belong to the same channel network when they share a side, so up, down, left or right. Meeting only at a corner joins nothing.

A network holding at least one cell on the outer rim of the sheet can vent to the air outside, and the plant leaves it alone. A network with no cell on the rim is a trapped pocket, and every cell of such a network is filled with solid material.

Do the filling where the sheet already sits. Overwrite the cells of sheet itself instead of assembling a second grid of the same size, then hand sheet back.

Examples

Example 1

Input
sheet = [["O", "X", "X"], ["X", "O", "X"], ["X", "X", "O"]]
Output
[["O", "X", "X"], ["X", "X", "X"], ["X", "X", "O"]]

The two corner cells sit on the rim and stay open. The middle cell only meets them at corners, which joins nothing, so it is a pocket of its own and gets filled.

Example 2

Input
sheet = [["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "O", "O", "X"], ["X", "X", "X", "X"]]
Output
[["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"]]

The four open cells form one network ringed by solid material on all sides, so the whole pocket is filled and the sheet ends up solid.

Example 3

Input
sheet = [["X", "O", "X"], ["O", "O", "X"], ["X", "X", "X"]]
Output
[["X", "O", "X"], ["O", "O", "X"], ["X", "X", "X"]]

All three open cells are one network, and two of them lie on the rim, so the network vents and the sheet is returned untouched.

Constraints

  • rows == sheet.length
  • cols == sheet[0].length
  • 1 <= rows, cols <= 200
  • sheet[r][c] is either "X" or "O".
  • The sheet must be filled in place: the grid returned is the grid that was passed in, not a copy.

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 seal_pockets(sheet: list[list[str]]) -> list[list[str]]:
Java
public char[][] sealPockets(char[][] sheet)

More on the same topics