Katkat
Back

Reveal a Minesweeper Board

NuroSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests recursive graph traversal (DFS/BFS) and grid manipulation logic to implement the recursive uncovering mechanism found in Minesweeper.

Problem Statement

You are given a 2D Minesweeper board as a list of lists of characters, where 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, and 'B' represents a revealed blank square (no adjacent mines). Digits '1'-'8' represent revealed squares with that many adjacent mines.

Implement a function reveal(board, row, col) that updates the board based on a user click at (row, col):

  1. If a mine ('M') is clicked, change it to 'X' (game over).
  2. If an empty square ('E') is clicked, check its eight neighbors:
    • If there are adjacent mines, change the square to the count of adjacent mines ('1'-'8').
    • If there are no adjacent mines, change the square to 'B' and recursively reveal all eight neighboring squares.
  3. If a revealed square is clicked, do nothing.

Function Signature

def reveal(board: List[List[str]], row: int, col: int) -> List[List[str]]:

Examples

Input:

board = [['E', 'E', 'E'],
         ['E', 'M', 'E'],
         ['E', 'E', 'E']]
row = 0, col = 0

Output:

[['1', '1', '1'],
 ['1', 'M', '1'],
 ['1', '1', '1']]

Explanation: Clicking (0,0) reveals a '1' because there is one mine at (1,1).

Constraints

  • The board is size m x n where 1 <= m, n <= 50.
  • board[i][j] is only 'M', 'E', 'B', or '1'-'8'.
  • Handle boundaries properly to avoid index out-of-bounds errors.

Hints

Hint 1

Use a helper function to count the number of mines adjacent to a given cell (r, c).

Hint 2

For the recursive expansion, only proceed to the next cell if the current cell is 'E' and has zero adjacent mines.

Hint 3

Ensure you mark cells as visited or change their state from 'E' to 'B' immediately to prevent infinite recursion.

Follow-up questions

  • How would your implementation change if the board size was extremely large (e.g., 10,000 x 10,000) and you needed to minimize memory usage?
  • How would you modify the algorithm to reveal only a specific number of squares per click, rather than clearing the entire empty region at once?
  • If the board was stored in a sparse format (e.g., a dictionary of only mine locations), how would you optimize the neighbor count lookup?