Minesweeper

Let's play the minesweeper 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, 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 = [click_r, click_c] 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: If a mine 'M' is revealed, then the game is over. You should change it to 'X'. 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. 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. Return the board when no more squares will be revealed. For example, given board = [['E','E','E','E','E'],['E','E','M','E','E'],['E','E','E','E','E'],['E','E','E','E','E']] and click = [3,0], the expected output is [['B','1','E','1','B'],['B','1','M','1','B'],['B','1','1','1','B'],['B','B','B','B','B']].

class Solution:
    def updateBoard(self, board: list[list[str]], click: list[int]) -> list[list[str]]:
        row, col = click
        
        if board[row][col] == 'M':
            board[row][col] = 'X'
            return board

        def count_adjacent_mines(r, c):
            count = 0
            for i in range(max(0, r - 1), min(len(board), r + 2)):
                for j in range(max(0, c - 1), min(len(board[0]), c + 2)):
                    if (i, j) != (r, c) and board[i][j] == 'M':
                        count += 1
            return count
        
        def reveal(r, c):
            if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) or board[r][c] != 'E':
                return
            
            mines = count_adjacent_mines(r, c)
            
            if mines > 0:
                board[r][c] = str(mines)
                return
            
            board[r][c] = 'B'
            
            for i in range(max(0, r - 1), min(len(board), r + 2)):
                for j in range(max(0, c - 1), min(len(board[0]), c + 2)):
                    if (i, j) != (r, c):
                        reveal(i, j)

        reveal(row, col)
        return board

Naive Approach:

The naive approach would be to iterate through the entire board for every click, which is not efficient. Instead, the given solution focuses on revealing only the necessary squares using Depth First Search (DFS).

Optimal Solution:

The optimal solution employs a recursive DFS approach, revealing squares based on the game's rules. When an empty square is clicked, it checks the adjacent squares for mines. If no mines are adjacent, it reveals adjacent squares recursively.

Big(O) Runtime Analysis:

• Time Complexity: O(M * N) in the worst case, where M is the number of rows and N is the number of columns in the board. This occurs when revealing a large area with no mines, requiring a visit to each cell. Although it looks like O(1) because the maximum size is fixed at 50, from an academic perspective, it is O(M * N). The count_adjacent_mines function takes O(1) time since it checks at most 8 neighbors.

Big(O) Space Usage Analysis:

• Space Complexity: O(M * N) in the worst case, where M is the number of rows and N is the number of columns in the board. This occurs when the call stack grows due to the recursive calls to reveal. In the worst-case scenario, almost the entire board may be revealed which requires keeping the function calls on the stack.

Edge Cases:

1. Clicking on a Mine ('M'): The game ends, and the mine is revealed as 'X'.
2. Clicking on an Empty Square ('E') with Adjacent Mines: The square is changed to a digit representing the number of adjacent mines.
3. Clicking on an Empty Square ('E') with No Adjacent Mines: The square is changed to 'B', and adjacent squares are revealed recursively.
4. Invalid Click (Out of Bounds): Handled implicitly by the conditional check at the beginning of the reveal function.
5. Board Dimensions: The code handles various board sizes within the constraints (1 <= m, n <= 50).