Katkat

Implement Minesweeper click-to-reveal expansion

Nash AISoftware Engineer · Technical Screen

Last 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:

  1. If a mine ('M') is clicked, change it to 'X' and the game is over.
  2. 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').
  3. 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 n grid, 1 <= m, n <= 50.
  • click is 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?