We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minesweeper

Difficulty: Medium

Problem Description

You are given an m x n char matrix board representing the game board for Minesweeper. You must reveal the square at a given click position according to specific rules based on whether the square is a mine, an empty square, or a square with adjacent mines.

Key Insights

  • The board consists of different cell types: unrevealed mines ('M'), unrevealed empty squares ('E'), revealed blanks ('B'), numbers ('1' to '8'), and revealed mines ('X').
  • If a mine is revealed, the game ends and the mine is marked.
  • If an empty square with no adjacent mines is revealed, it becomes 'B' and adjacent unrevealed squares should be revealed recursively.
  • If an empty square has adjacent mines, it should show the count of those mines.

Space and Time Complexity

Time Complexity: O(m * n) in the worst case, where every cell may need to be revealed. Space Complexity: O(m * n) for the recursive call stack in the case of DFS.

Solution

To solve the problem, we use a depth-first search (DFS) or breadth-first search (BFS) approach. We check the clicked cell:

  1. If it's a mine ('M'), we change it to 'X' and return.
  2. If it's an empty cell ('E'), we count adjacent mines:
    • If there are no adjacent mines, we mark it as 'B' and recursively reveal its neighbors.
    • If there are adjacent mines, we mark it with the count. We maintain the board's state throughout the process.

Code Solutions

def updateBoard(board, click):
    rows, cols = len(board), len(board[0])
    r, c = click

    if board[r][c] == 'M':
        board[r][c] = 'X'
        return board

    def countMines(r, c):
        count = 0
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if 0 <= r + dr < rows and 0 <= c + dc < cols and board[r + dr][c + dc] == 'M':
                    count += 1
        return count

    def dfs(r, c):
        if board[r][c] != 'E':
            return
        mine_count = countMines(r, c)
        if mine_count > 0:
            board[r][c] = str(mine_count)
            return
        board[r][c] = 'B'
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    dfs(nr, nc)

    dfs(r, c)
    return board
← Back to All Questions