algoadvance

You are given a 2D char matrix representing the game board and a list of click positions. The board consists of the following characters:

• ‘M’ represents an unrevealed mine,
• ‘E’ represents an unrevealed empty square,
• ‘B’ represents a revealed blank square that has no adjacent mines (all surrounding squares are either ‘B’ or ‘E’),
• digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and
• ‘X’ represents a revealed mine.

You are supposed to handle clicks in the following way:

1. If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.
2. If an empty square (‘E’) with no adjacent mines is revealed, then change it to 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.

Return the board after processing all the given clicks.

The click positions are given in an array of arrays clicks, where each element is an array [i, j] that represents the row index and column index of the board where the user clicked.

Clarifying Questions

1. Will the clicks always be within the board boundaries?
2. How many clicks can be provided in the list of clicks?
3. Can the same cell be clicked more than once?

Suppose the answer is:

1. Yes, the clicks will always be within the board boundaries.
2. The list of clicks can be of any size.
3. Yes, the same cell can be clicked more than once.

Strategy

1. For each click:
   • If the cell contains a mine (‘M’), change it to ‘X’ and the game is over for that click.
   • If the cell is an empty square (‘E’):
     • Count the number of adjacent mines.
     • If there are adjacent mines, change the cell to the corresponding number (‘1’ to ‘8’).
     • If no adjacent mines, change the cell to ‘B’ and recursively reveal adjacent cells.
2. Continue processing each click in the given list of clicks.

Code

def updateBoard(board, clicks):
    def count_adjacent_mines(x, y):
        mines_count = 0
        for dx, dy in [(-1, -1), (-1, 0), (-1, 1), 
                       ( 0, -1),         ( 0, 1), 
                       ( 1, -1), ( 1, 0), ( 1, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] == 'M':
                mines_count += 1
        return mines_count

    def reveal(x, y):
        if board[x][y] != 'E':
            return
        adjacent_mines = count_adjacent_mines(x, y)
        if adjacent_mines > 0:
            board[x][y] = str(adjacent_mines)
        else:
            board[x][y] = 'B'
            for dx, dy in [(-1, -1), (-1, 0), (-1, 1), 
                           ( 0, -1),         ( 0, 1), 
                           ( 1, -1), ( 1, 0), ( 1, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < len(board) and 0 <= ny < len(board[0]):
                    reveal(nx, ny)

    for click in clicks:
        x, y = click
        if board[x][y] == 'M':
            board[x][y] = 'X'
        else:
            reveal(x, y)
    
    return board

Time Complexity

• Each cell can be revealed only once, and the algorithm handles each cell and its adjacent cells.
• The time complexity primarily involves exploring all cells in the worst case, leading to O(N * M) where N is the number of rows and M is the number of columns in the board.

By following this strategy, we can correctly simulate the Minesweeper game as per the given problem statement and clicks.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?