529. Minesweeper - Detailed Explanation

Problem Statement

Description:
You are given a 2D board representing a Minesweeper game. Each cell on the board can be one of the following characters:

• 'M' – an unrevealed mine,
• 'E' – an unrevealed empty square,
• 'B' – a revealed blank square with no adjacent mines,
• '1' to '8' – a revealed square indicating the number of adjacent mines,
• 'X' – a revealed mine (game over).

You are also given a click position (a pair of row and column indices). Based on the click, update the board as follows:

1. Mine Clicked:
   If a mine ('M') is clicked, change it to 'X' to mark that the game is over.
2. Empty Square Clicked (No Adjacent Mines):
   If an empty square ('E') with no adjacent mines is revealed, change it to a blank ('B'). Then, recursively reveal all of its adjacent unrevealed squares.
3. Empty Square Clicked (With Adjacent Mines):
   If an empty square ('E') with one or more adjacent mines is revealed, change it to a digit ('1' to '8') representing the number of adjacent mines.
4. Stop Condition:
   Return the updated board when no more squares can be revealed.

Examples:

• 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']]
  

  Explanation:
  The click at position [3, 0] (bottom-left corner) reveals an empty square with no adjacent mines. A recursive reveal then occurs to all adjacent squares. For squares adjacent to a mine, the count is shown.

• 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']]
  

  Explanation:
  The click at position [1, 2] hits a mine. The mine is then revealed as 'X', indicating game over.

Constraints:

• The board is a 2D array of characters.
• The click is a valid coordinate within the board.
• Board dimensions and the number of mines/empty squares vary, but you can assume the board is not empty.

Hints Before Diving into the Solution

• Hint 1:
  Think about how you can explore the board in all 8 directions (up, down, left, right, and the 4 diagonals) from any given cell. This is crucial for counting adjacent mines and for the recursive reveal.

• Hint 2:
  When revealing cells, consider using either Depth-First Search (DFS) or Breadth-First Search (BFS). What conditions will determine whether you should stop the search in a certain direction?

Approach 1: Depth-First Search (DFS)

Idea:

1. Click a Mine:
   If the clicked cell is 'M', update it to 'X' and return immediately.

2. Reveal an Empty Cell:
   If the clicked cell is 'E', count the number of adjacent mines by exploring all 8 directions.

   • No Adjacent Mines:
     If the count is zero, change the cell to 'B' and recursively reveal all adjacent unrevealed cells.
   • Adjacent Mines Present:
     If the count is greater than zero, update the cell with the count (as a character) and stop further exploration from that cell.

Visual Walkthrough:

Imagine a cell at position (i, j). For each of the 8 directions (e.g., (i-1, j), (i+1, j), (i, j-1), (i, j+1), and the four diagonals), check if the cell contains a mine ('M').

• If zero mines are adjacent, mark it as 'B' and perform DFS on its neighbors.
• If there are mines present, update the cell with the number of mines and do not explore its neighbors.

Approach 2: Breadth-First Search (BFS)

Idea:

1. Use a Queue:
   Start by adding the clicked cell to a queue.
2. Process Each Cell:
   While the queue is not empty:
   • Remove a cell from the queue.
   • If it is an empty cell ('E'), count adjacent mines.
   • If the count is zero, mark the cell as 'B' and enqueue all adjacent unrevealed cells.
   • Otherwise, update the cell with the count.
3. Stop When Done:
   Continue until there are no cells left to process in the queue.

Comparison:

• DFS is naturally recursive and might be easier to implement, but it could run into deep recursion issues on large boards.
• BFS uses an iterative approach with a queue, which can help avoid recursion depth problems and might be preferred when the board is large.

Python Code