Minesweeper: Matrix DFS with Recursive Reveal

You are given an m x n board representing a Minesweeper game. Each cell is one of: 'M' (unrevealed mine), 'E' (unrevealed empty), 'B' (revealed blank with no adjacent mines), a digit '1' to '8' (count of adjacent mines), or 'X' (a revealed/clicked mine). Given a click position, update the board according to the game rules and return it.

This is LeetCode 529: Minesweeper, and it is a clean exercise in matrix DFS. The twist compared to problems like Number of Islands is that your DFS does not blindly flood fill everything. Instead, it makes a decision at each cell: count adjacent mines, and only recurse further if that count is zero. That conditional recursion is the core of the problem.

The problem

The rules mirror the real game:

1. If you click on a mine ('M'), change it to 'X' (game over) and return the board.
2. If you click on an empty cell ('E'), count the adjacent mines in all 8 directions. If the count is greater than zero, change the cell to the corresponding digit character. If the count is zero, change it to 'B' and recursively reveal all 8 adjacent unrevealed cells.

Here is an example. The board has three mines. Clicking on (4,0), far from any mine, triggers a cascade of reveals:

The key insight

This is DFS on a matrix, but with a branching condition. At each cell you visit, you count how many of the 8 neighbors are mines. If the count is positive, you write the digit and stop. If the count is zero, you write 'B' and recurse into all 8 neighbors. The numbered cells act as a natural boundary that halts the DFS expansion.

The solution

def update_board(board: list[list[str]], click: list[int]) -> list[list[str]]:
    rows, cols = len(board), len(board[0])
    r, c = click

    # Rule 1: clicked a mine
    if board[r][c] == "M":
        board[r][c] = "X"
        return board

    # 8 directions: up, down, left, right, and 4 diagonals
    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1),
    ]

    def dfs(r: int, c: int) -> None:
        # Count adjacent mines
        mine_count = 0
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "M":
                mine_count += 1

        if mine_count > 0:
            # Adjacent to at least one mine: write the count, stop
            board[r][c] = str(mine_count)
        else:
            # No adjacent mines: blank cell, recurse into neighbors
            board[r][c] = "B"
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "E":
                    dfs(nr, nc)

    dfs(r, c)
    return board

Step-by-step walkthrough

Let's trace through the DFS reveal starting from click position (4,0) on a 5x5 board with mines at (0,2), (2,1), and (3,4).

Notice how the DFS expands through blank cells and stops the moment a cell has at least one adjacent mine. The numbered cells form a ring around the revealed blank region.

Complexity analysis

Time: O(m * n) where m is rows and n is columns. Each cell is visited at most once. The DFS marks cells as 'B' or a digit before recursing, so no cell is processed twice.

Space: O(m * n) worst case for the recursion stack. If the entire board has no mines, every cell becomes 'B' and the DFS recurses through all of them. In practice, mines break the board into smaller regions, keeping the recursion shallow.

The building blocks

1. Eight-direction neighbor generation

Unlike problems that use 4-directional movement, Minesweeper counts and moves in all 8 directions (including diagonals):

directions = [
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),           (0, 1),
    (1, -1),  (1, 0),  (1, 1),
]
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # (nr, nc) is a valid neighbor

This is the same direction array pattern from Number of Islands, just expanded to 8 entries. The bounds check prevents index errors. You will use the 8-direction version in problems like Game of Life, where diagonal adjacency matters.

2. Conditional DFS (count then decide)

The standard flood fill pattern visits a cell and immediately recurses. Minesweeper adds a decision step: count adjacent mines first, then decide whether to recurse or stop.

def dfs(r, c):
    count = count_adjacent_mines(r, c)
    if count > 0:
        board[r][c] = str(count)  # stop here
    else:
        board[r][c] = "B"         # blank, keep going
        for each neighbor:
            if neighbor is unrevealed:
                dfs(neighbor)

This conditional recursion pattern shows up whenever your DFS needs to decide at each node whether to keep expanding or to treat the current node as a boundary. It is a slight generalization of the pure flood fill, and recognizing it quickly saves time in interviews.

Edge cases

• Click on a mine: Return immediately after changing 'M' to 'X'. No DFS needed.
• Click on a cell adjacent to mines: The cell gets a digit, and nothing else happens. No recursion.
• Board with no mines: Every cell becomes 'B'. The DFS visits the entire board.
• Single cell board: If it is 'M', return 'X'. If it is 'E', return 'B' (no neighbors to count).
• Already revealed cells: The problem guarantees the click is on an unrevealed cell ('M' or 'E'), so you do not need to handle clicks on revealed cells.

From understanding to recall

You have seen how the DFS reveal works. The algorithm itself is not complicated: count neighbors, decide whether to recurse, mark the cell. But under interview pressure, the details trip people up. Do you check 'E' before recursing or after? Do you mark the cell before or after counting? Do you use 4 directions or 8?

These are recall problems, not understanding problems. Spaced repetition drills the specific sequence of operations until you can write the DFS function without hesitating. The conditional recursion pattern (count, then decide) is a reusable brick that applies to any problem where DFS expansion depends on local conditions.

Related posts

• Number of Islands - The foundational grid DFS problem with pure flood fill
• Surrounded Regions - Grid DFS from the border inward, another twist on the basic pattern
• Pacific Atlantic Water Flow - Multi-source grid DFS with directional constraints