Minesweeper

Problem Id: 529 Difficulty: Medium


Intuition

Solution


class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        self.cache = {}
        i, j = click
        if board[i][j] == 'M':
            board[i][j] = 'X'
            return board

        count = [[0] * len(board[0]) for _ in board]
        for x in range(len(board)):
            for y in range(len(board[0])):
                if board[x][y] == 'M':
                    for m in range(max(x - 1, 0), min(x + 2, len(board))):
                        for n in range(max(y - 1, 0), min(y + 2, len(board[0]))):
                            count[m][n] += 1

        bfs = [(i, j)]
        test = 0
        while bfs:
            i, j = bfs.pop()
            c = count[i][j]
            if c > 0:
                board[i][j] = str(c)
                continue
            board[i][j] = 'B'
            for x in range(max(i - 1, 0), min(i + 2, len(board))):
                for y in range(max(j - 1, 0), min(j + 2, len(board[0]))):
                    if board[x][y] == 'E':
                        bfs.append((x, y))
        return board