Graph Real-Life Problems

What is this?

Most graph problems make you find the algorithm. This one hands it to you — it is a flood fill — and then makes the rules the difficulty. Clicking a square in Minesweeper does one of three things depending on what is underneath and what surrounds it, and only one of those three continues the flood.

Getting this right is a test of reading comprehension and case discipline rather than algorithmic insight, which is exactly why it appears in interviews.

💡 Fun fact: the rule that a numbered square stops the flood is what makes Minesweeper playable. If revealing a square with adjacent mines also revealed its neighbours, one click would cascade across the entire board and the game would be over immediately. The numbers are the walls of the flood fill — the whole game design rests on that single "do not recurse" branch.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: the traversal is an ordinary 8-directional flood fill. The problem is entirely in the branch structure — count first, then decide whether to recurse — and in remembering that a numbered cell is a wall, not a doorway.

1. Count before you recurse

The single most common wrong implementation recurses first and counts afterwards. The order must be:

def reveal(board, r, c):
    if board[r][c] == 'M':
        board[r][c] = 'X'                    # hit a mine — stop entirely
        return

    mines = count_adjacent_mines(board, r, c)   # count BEFORE deciding
    if mines > 0:
        board[r][c] = str(mines)                # a wall — do not expand
        return

    board[r][c] = 'B'                            # empty — expand
    for dr, dc in EIGHT_DIRECTIONS:
        nr, nc = r + dr, c + dc
        if in_bounds(nr, nc) and board[nr][nc] == 'E':
            reveal(board, nr, nc)

Three exits, and only the last one recurses. The guard board[nr][nc] == 'E' doubles as the visited check — once a cell has been changed to B or a digit it is no longer E, so it will not be processed twice. No separate visited set is needed, which is a small, satisfying consequence of mutating the board in place.

2. Eight directions, not four

Adjacency here includes diagonals, so both the mine count and the expansion use all eight offsets:

EIGHT_DIRECTIONS = [(-1,-1), (-1,0), (-1,1),
                    ( 0,-1),         ( 0,1),
                    ( 1,-1), ( 1,0), ( 1,1)]

Writing four directions by habit produces a board that looks almost right and is wrong along every diagonal — the kind of bug that passes a small test and fails a large one.

3. A 30-second worked example

board            click (3,0), which is 'E' with no adjacent mines
E E E E E
E E M E E        after revealing:
E E E E E        B 1 E 1 B
E E E E E        B 1 M 1 B
                 B 1 1 1 B
                 B B B B B

The flood spreads through every empty cell but stops at the ring of numbered cells around the mine. Those cells are revealed — they show their counts — but they are not expanded through, which is why the mine's neighbourhood stays hidden behind them.

4. Where you'll actually meet this

• Game development. Fog-of-war reveal, territory capture and cascading tile updates are all conditional flood fills.
• Image editing. The paint-bucket tool floods until a boundary condition is met — a colour difference threshold rather than a mine count, but the same branch structure.
• Spreadsheet recalculation. Propagating a change until a cell with no dependents is reached.
• Geographic analysis. Flood modelling that stops at barriers, where the barrier condition is computed per cell.
• Alert and incident propagation. Cascading failures through a dependency graph, halting at components with their own fallbacks.

5. Problems in this chapter

▶ Minesweeper

Reveal a board given a click. Mine becomes X; a cell with adjacent mines shows the count and stops; an empty cell becomes B and expands to all eight neighbours.
Pattern: conditional 8-directional flood fill. Target: O(mn) time, O(mn) recursion depth in the worst case.

6. Common pitfalls 🚫

• Recursing before counting. The count decides whether to recurse at all; doing it the other way round floods the whole board.
• Using four directions. Minesweeper adjacency is all eight, for both the count and the expansion.
• Expanding through numbered cells. They are revealed but never recursed into — this is the rule the whole game depends on.
• Forgetting the mine case. A click directly on a mine sets X and does nothing else.
• Adding a visited set. Unnecessary — mutating E into B or a digit already prevents reprocessing.
• Missing bounds checks in the diagonal offsets. Corners are where the index errors live.
• Recursion depth on a large empty board. An entirely empty grid can recurse m × n deep; mention the iterative stack version.

7. Key takeaways

1. The algorithm is the easy part. Read the specification twice; the branches are the problem.
2. Count first, then decide. The mine count determines whether this cell is a wall or a doorway.
3. Numbered cells stop the flood — without that rule the game would not exist.
4. Eight directions, consistently, in both the count and the expansion.
5. Mutation can serve as the visited set when the problem lets you write into the input.
6. Watch the recursion depth on large uniform grids.
7. Why interviewers like it: it is deliberately unglamorous. It measures whether you implement a stated specification exactly, which is most of the job.

Order: Minesweeper.