{x}
blog image

Minesweeper

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),
  • digit ('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:

  1. If a mine 'M' is revealed, then the game is over. You should change it to 'X'.
  2. If an empty square '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.
  3. If an empty square 'E' with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
  4. Return the board when no more squares will be revealed.

 

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.length
  • n == board[i].length
  • 1 <= m, n <= 50
  • board[i][j] is either 'M', 'E', 'B', or a digit from '1' to '8'.
  • click.length == 2
  • 0 <= clickr < m
  • 0 <= clickc < n
  • board[clickr][clickc] is either 'M' or 'E'.

Solution Explanation for Minesweeper

This problem involves implementing the logic of the classic Minesweeper game. The goal is to reveal the game board based on a user's click, adhering to specific rules. The optimal approach is Depth-First Search (DFS).

Algorithm:

  1. Handle Mine Click: If the clicked cell contains a mine ('M'), immediately change it to 'X' and return the board.

  2. Depth-First Search (DFS): If the clicked cell is empty ('E'), perform a DFS to reveal adjacent cells.

    • Count Adjacent Mines: For the current cell, count the number of mines in its eight neighboring cells.
    • Reveal Cell:
      • If the count is greater than 0, update the cell with the count (as a digit character).
      • If the count is 0, update the cell to 'B' (blank) and recursively call dfs for all its unrevealed ('E') neighbors. This recursive step ensures that all connected empty cells without adjacent mines are revealed.

Code Explanation (Python):

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        def dfs(i: int, j: int):
            cnt = 0
            for x in range(i - 1, i + 2):
                for y in range(j - 1, j + 2):
                    if 0 <= x < m and 0 <= y < n and board[x][y] == "M":
                        cnt += 1
            if cnt:
                board[i][j] = str(cnt)
            else:
                board[i][j] = "B"
                for x in range(i - 1, i + 2):
                    for y in range(j - 1, j + 2):
                        if 0 <= x < m and 0 <= y < n and board[x][y] == "E":
                            dfs(x, y)
 
        m, n = len(board), len(board[0])
        i, j = click
        if board[i][j] == "M":
            board[i][j] = "X"
        else:
            dfs(i, j)
        return board

The Python code efficiently implements the algorithm. The dfs function recursively explores the board, revealing empty cells and counting mines in their vicinity. Boundary conditions are handled to prevent out-of-bounds errors.

Time and Space Complexity:

  • Time Complexity: O(M*N) in the worst case, where M and N are the dimensions of the board. This is because in the worst case, we might need to visit every cell on the board if all cells are empty and interconnected. The DFS explores each cell at most once.

  • Space Complexity: O(MN) in the worst case due to the recursive calls in DFS. The maximum depth of the recursion can be proportional to the number of cells in the largest connected component of empty cells. In practice, it's often much less than O(MN).

The provided code in other languages (Java, C++, Go, TypeScript) follows the same algorithmic approach, differing only in syntax and language-specific features. The complexity analysis remains consistent across all implementations.