Let's play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
'M' represents an unrevealed mine,'E' represents an unrevealed empty square,'B' represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),'1' to '8') represents how many mines are adjacent to this revealed square, and'X' represents a revealed mine.You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares ('M' or 'E').
Return the board after revealing this position according to the following rules:
'M' is revealed, then the game is over. You should change it to 'X'.'E' with no adjacent mines is revealed, then change it to a revealed blank 'B' and all of its adjacent unrevealed squares should be revealed recursively.'E' with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.Example 1:
Input: board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0] Output: [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]
Example 2:
Input: board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2] Output: [["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 50board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'.click.length == 20 <= clickr < m0 <= clickc < nboard[clickr][clickc] is either 'M' or 'E'.The Minesweeper problem simulates revealing cells on a game board after a user click. The board is represented as a matrix, and the key idea is to reveal cells recursively when there are no adjacent mines. If a clicked cell contains a mine, it immediately changes to 'X'. Otherwise, you must count the number of surrounding mines in the 8 possible directions.
If the count of adjacent mines is greater than zero, update the cell with that number. If the count is zero, mark the cell as 'B' and reveal all neighboring unrevealed cells. This expansion naturally fits Depth-First Search (DFS) or Breadth-First Search (BFS) traversal on a grid.
The algorithm processes each cell at most once, ensuring efficiency. Careful boundary checks and direction vectors help simplify neighbor traversal. Both DFS recursion and BFS queue-based traversal achieve similar performance while exploring safe regions of the board.
Time Complexity: O(m × n) in the worst case when large empty regions are revealed. Space Complexity: O(m × n) due to recursion stack or queue usage during traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (DFS) | O(m × n) | O(m × n) |
| Breadth-First Search (BFS) | O(m × n) | O(m × n) |
Greg Hogg
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
DFS and BFS are ideal for exploring connected regions in a grid. When a cell has no adjacent mines, the algorithm must reveal all neighboring cells, which naturally becomes a graph traversal problem.
The optimal approach uses Depth-First Search (DFS) or Breadth-First Search (BFS) to reveal connected empty cells. When a clicked cell has no adjacent mines, the algorithm recursively explores neighboring cells until numbered boundaries are reached.
Yes, Minesweeper-style grid traversal problems appear in coding interviews, especially at companies that test matrix traversal and graph exploration skills. It evaluates understanding of DFS, BFS, and boundary handling.
A matrix is used to represent the board, while DFS uses recursion and BFS uses a queue for traversal. Direction arrays are commonly used to check all eight neighboring cells efficiently.