Implement Minesweeper click-to-reveal expansion
Nash AISoftware Engineer · Technical ScreenLast updated
This problem tests your ability to implement recursive traversal (flood-fill) on a 2D grid and manage game state transitions based on player input.
Minesweeper Click Logic
Implement the core 'click' functionality for a Minesweeper game. You are given a grid represented by a 2D list of characters where 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, and 'B' represents a revealed blank square.
You are also given a list click representing the row and column of the user's move.
Rules:
- If a mine (
'M') is clicked, change it to'X'and the game is over. - If an unrevealed empty square (
'E') is clicked:- If the square has one or more adjacent mines (including diagonals), reveal the number of adjacent mines and update the square to that digit (as a string).
- If the square has zero adjacent mines, change it to
'B'and recursively reveal all adjacent unrevealed empty squares ('E').
- If a revealed square is clicked, do nothing.
Function Signature
def updateBoard(board: list[list[str]], click: list[int]) -> list[list[str]]:
Examples
Example 1:
Input: board = [['E', 'E'], ['E', 'M']], click = [0, 0]
Output: [['1', '1'], ['1', 'M']]
Explanation: Clicking (0,0) reveals a square adjacent to one mine at (1,1).
Example 2:
Input: board = [['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B']], click = [1, 2]
Output: [['B', '1', 'E', '1', 'B'], ['B', '1', 'X', '1', 'B']]
Explanation: Clicking a mine turns it into 'X'.
Constraints
m x ngrid,1 <= m, n <= 50.clickis a valid coordinate.- The board only contains 'M', 'E', 'B', or digits '1'-'8'.
Hints
Hint 1
Use a helper function to count the number of mines adjacent to a given cell (r, c).
Hint 2
A Breadth-First Search (BFS) or Depth-First Search (DFS) is appropriate for cascading reveals when a cell has zero adjacent mines.
Hint 3
Make sure to check boundary conditions (row/column indices) when looking at neighbors to avoid index-out-of-bounds errors.
Follow-up questions
- How would you optimize the mine-counting step if the board were very large and the user clicked many times?
- How would you handle the requirement of 'flagging' a square so it cannot be clicked?
- What changes are needed if the board is represented by a sparse data structure rather than a 2D array?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.