529. Minesweeper - cocoder39/coco39_LC GitHub Wiki

529. Minesweeper

• the first cell to be revealed is either M or E
• recursively reveal an adjacent cell only if none of the 8 adjacent cell is mine. so the adjacent cell to be revealed is for sure not mine.
• recursively reveal an adjacent cell only if the cell is not revealed, so the value of the cell before being revealed is always E
• X can only come from a direct reveal. It cannot be from a indirect recursive reveal, because recursive reveal happens only if the cell to be revealed has no adjacent mine

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        m, n = len(board), len(board[0])
        DIR = [(1, -1), (0, -1), (-1, -1), (1, 0), (-1, 0), (1, 1), (0, 1), (-1, 1)]

        def discover(row, col):
            if board[row][col] == 'M':
                board[row][col] = 'X'
                return
            
            if board[row][col] == 'E':
                mine_count = 0
                for dr, dc in DIR:
                    new_row, new_col = row + dr, col + dc
                    if 0 <= new_row < m and 0 <= new_col < n:
                        if board[new_row][new_col] == 'M':
                            mine_count += 1
                        
                if mine_count:
                    board[row][col] = str(mine_count)
                else:
                    board[row][col] = 'B'
                    for dr, dc in DIR:
                        new_row, new_col = row + dr, col + dc
                        if 0 <= new_row < m and 0 <= new_col < n and board[new_row][new_col] == 'E':
                            discover(new_row, new_col)
        
        discover(click[0], click[1])
        return board