A grid is a graph

Cells are nodes, adjacency is edges, and the visited mark is permanent. That last word is the whole lesson.

Why it works

Marked once, never unmarked

In Unit 10 the grid mark was undone on the way out, because every distinct path mattered. Here it is not, because arriving at a cell once is enough to know it belongs to this region.

That single difference is the whole cost story, and it is worth seeing as a number rather than as an assertion. Below, the same two-by-two board is walked twice: once marking permanently, once undoing the mark the way a path search would.

1board = [["X", "X"],2         ["X", "X"]]3neighbors = {(0, 0): [(0, 1), (1, 0)], (0, 1): [(0, 0), (1, 1)],4             (1, 0): [(0, 0), (1, 1)], (1, 1): [(0, 1), (1, 0)]}5 6visits = 07def walk(cell, seen, undo):8    global visits9    visits += 110    seen.add(cell)11    for nxt in neighbors[cell]:12        if nxt not in seen:13            walk(nxt, seen, undo)14    if undo:15        seen.remove(cell)16 17walk((0, 0), set(), undo=False)18print("permanent marks, cell visits:", visits)19 20visits = 021walk((0, 0), set(), undo=True)22print("marks undone, cell visits:  ", visits)

Four cells against seven visits, on a board of only four. The gap is exponential in the region size, so on a real grid it is not a constant factor.

Code lab· 26 min

Flood fill drills

Three readings of one traversal, none of which is a plain count. region_of returns the sorted cells of the region containing a given cell. bounding_box returns the smallest rectangle enclosing that region, as [top, left, bottom, right]. regions_touching_border counts how many separate regions of X touch any edge of the board. Cells connect side to side only, not diagonally.

solution.py

Tests

board = [    ["X", "X", ".", "."],    ["X", ".", ".", "X"],    [".", ".", "X", "X"],]print(region_of(board, 0, 0))print(bounding_box(board, 0, 0), bounding_box(board, 2, 3))print(region_of(board, 0, 2), bounding_box(board, 0, 2))print(regions_touching_border(board), regions_touching_border([[".", "."]]))

Output

Run tests to see output.

Problem· 22 min

Number Of Islands

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 18 min

Max Area Of Island

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1board = [["X", "X"],2 ["X", "X"]]3neighbors = {(0, 0): [(0, 1), (1, 0)], (0, 1): [(0, 0), (1, 1)],4 (1, 0): [(0, 0), (1, 1)], (1, 1): [(0, 1), (1, 0)]}5 6visits = 07def walk(cell, seen, undo):8 global visits9 visits += 110 seen.add(cell)11 for nxt in neighbors[cell]:12 if nxt not in seen:13 walk(nxt, seen, undo)14 if undo:15 seen.remove(cell)16 17walk((0, 0), set(), undo=False)18print("permanent marks, cell visits:", visits)19 20visits = 021walk((0, 0), set(), undo=True)22print("marks undone, cell visits: ", visits)

board = [ ["X", "X", ".", "."], ["X", ".", ".", "X"], [".", ".", "X", "X"],]print(region_of(board, 0, 0))print(bounding_box(board, 0, 0), bounding_box(board, 2, 3))print(region_of(board, 0, 2), bounding_box(board, 0, 2))print(regions_touching_border(board), regions_touching_border([[".", "."]]))