progress

~/problems / Graphs / DFS and connected components

Surrounded Regions

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~25 min

A floor plan is drawn on a grid of "#" (wall) and "." (open floor). Open cells joined horizontally or vertically form pockets. A pocket that touches the outer border of the grid lets air in from outside; a pocket that touches no border cell is sealed, and the builders want to pour concrete into it.

Implement fill_sealed(grid) -> None, which changes grid in place: every open cell in a sealed pocket becomes "#". Open cells whose pocket reaches the border (diagonals don't count) stay ".". Return nothing.

grid = [
    list("#####"),
    list("#..##"),
    list("##.#."),
    list("#.###"),
    list("#.###"),
]
fill_sealed(grid)
# grid is now
# #####
# #####
# ####.     (the "." on the right edge touches the border)
# #.###     (this pocket runs down to the bottom row)
# #.###
A 5 by 5 floor plan: a three-cell pocket in the upper middle touches no border and is filled, while the cell on the right edge and the two-cell pocket running to the bottom stay open.
the pink pocket is sealed and gets filled; the cyan cells reach the border
grid = [list("..."), list(".#."), list("...")]
fill_sealed(grid)
# unchanged: the only pocket is the ring, which is all border
  • 1 <= rows, cols <= 300.
  • A pocket can wind through most of the grid, so avoid deep recursion (Python's default limit is about 1,000 frames).
  • ⭐ Bonus: speed tests on large grids earn a star in O(rows·cols).
Show hint

Deciding for each pocket whether it is sealed is awkward. It is easier to find the cells that are definitely not sealed, starting from the border, and fill everything else.

Topic: DFS and connected components. Iterative DFS / flood fill; count and label components.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc