Minesweeper — Solution

Problem

You have a 2D Minesweeper board where each cell is either an unrevealed mine ('M'), an unrevealed empty square ('E'), a revealed blank ('B', meaning no adjacent mines), or a revealed digit ('1'–'8', the count of adjacent mines). Given a single click on one cell, update the board according to Minesweeper rules and return it.

The rules: if the clicked cell is a mine, mark it 'X' (game over). If it is empty, count its mines in all 8 directions — if that count is positive, reveal the digit; if zero, reveal 'B' and recursively reveal every unrevealed empty neighbor.

• Input: board above, click = [3, 0]
• Output: the board below
• Explanation: clicking a zero-mine cell triggers a chain reveal that stops at cells adjacent to the mine

Counter-example — clicking a mine ends the game immediately:

• Input: the same board, click = [1, 2] (the 'M' cell)
• Output: that cell becomes 'X', everything else unchanged

Intuition

When a cell has no adjacent mines it acts like an open corridor — there is nothing to hide, so Minesweeper automatically reveals every connected empty cell until it hits a wall of digits. This is exactly a DFS flood fill: the 'B' cells are the interior, the digit cells form the boundary, and you stop propagating the moment you cross it.

Solution — DFS Flood Fill

Starting from the clicked cell, count mines in all 8 neighbors. If the count is nonzero, write the digit and stop. If zero, write 'B' and recurse into every still-unrevealed empty neighbor.

1. If the clicked cell is 'M', set it to 'X' and return — game over.
2. Otherwise call dfs(row, col) on the click position.
3. In dfs: count all 'M' cells among the 8 neighbors.
4. If mine_count > 0, write str(mine_count) into the cell and return — no further spreading.
5. If mine_count == 0, write 'B' into the cell, then call dfs on every neighbor that is still 'E'.
6. The check board[nr][nc] == 'E' prevents re-entering already-revealed cells, guaranteeing termination.

1def updateBoard(board: list[list[str]], click: list[int]) -> list[list[str]]:
2    rows, cols = len(board), len(board[0])
3    row, col = click
4
5    if board[row][col] == 'M':
6        board[row][col] = 'X'
7        return board
8
9    def dfs(r: int, c: int) -> None:
10        mine_count = 0
11        for dr in [-1, 0, 1]:
12            for dc in [-1, 0, 1]:
13                if dr == 0 and dc == 0:
14                    continue
15                nr, nc = r + dr, c + dc
16                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'M':
17                    mine_count += 1
18
19        if mine_count > 0:
20            board[r][c] = str(mine_count)  # reveal digit and stop — do not spread past this wall
21        else:
22            board[r][c] = 'B'  # mark before recursing so neighbors skip this cell on their own pass
23            for dr in [-1, 0, 1]:
24                for dc in [-1, 0, 1]:
25                    if dr == 0 and dc == 0:
26                        continue
27                    nr, nc = r + dr, c + dc
28                    if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'E':
29                        dfs(nr, nc)
30
31    dfs(row, col)
32    return board

Time: O(m × n) — each cell is visited at most once since we only recurse into 'E' cells and immediately change them.

Space: O(m × n) — the DFS call stack depth is bounded by the total number of cells in the worst case where the entire board is one open region.

Complexity Summary

Common Mistakes

• Using only 4 directions instead of 8 — Minesweeper counts diagonal neighbors for both the mine tally and the spread; missing diagonals produces wrong digit values and an incorrect reveal region.
• Not marking the cell 'B' before recursing — if you flip the cell only after all 8 recursive calls return, every diagonal neighbor sees the current cell as still 'E' and recurses back into it, causing infinite mutual recursion.
• Spreading from digit cells — only cells with zero adjacent mines become 'B' and propagate; cells with a nonzero count reveal their digit and stop. Continuing to recurse from digit cells incorrectly reveals cells hidden behind the mine boundary.
• Including the current cell in its own mine count — the (dr == 0 && dc == 0) skip is essential; without it, a cell containing 'M' would count itself, inflating every adjacent cell's digit by one.
• Forgetting the mine-click branch — if board[row][col] == 'M', the cell should become 'X' immediately and no DFS should run; skipping this branch passes the mine position into the empty-cell logic and produces garbage output.

Related Problems

• Flood Fill — the same 4-directional flood-fill primitive, without the mine-counting boundary condition
• Number of Islands — DFS flood fill to mark and count connected components on a 2D grid
• 01 Matrix — BFS spreading outward from all zero-cells simultaneously, the BFS counterpart to this DFS
• Rotting Oranges — BFS grid spread that also distinguishes between source cells and boundary cells
• Max Area of Island — DFS flood fill that accumulates a size count rather than revealing neighbors