LeetCode | 0529. Minesweeper掃雷ゲーム【Medium】【Python】【DFS】

LeetCode 0529. Minesweeper掃雷ゲーム【Medium】【Python】【DFS】
Problem
LeetCode
Let’s play the minesweeper game (Wikipedia, online game)!
You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.
Now given the next click position (row and column indices) 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 - change it to ‘X’.

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.

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.

Example 1:

Input: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Example 2:

Input: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

Output: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Note:

The range of the input matrix’s height and width is [1,50].

The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.

The input board won’t be a stage when game is over (some mines have been revealed).

For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

に質問
スナップ
一緒に雷掃除ゲームをしましょう.
ゲームボードを表す2 D文字マトリクスを指定します.'Mは掘削されていない地雷を表し、「E」は掘削されていない空のブロックを表し、「B」は隣接していない(上、下、左、右、およびすべての4つの対角線)地雷の掘削された空白のブロックを表し、数字(「1」から「8」)はこの掘削されたブロックにどれだけの地雷が隣接しているかを表し、「X」は掘削された地雷を表す.
掘り出されていないすべてのブロック(‘M’または’E’)の次のクリック位置(行および列インデックス)が与えられ、以下のルールに従って、クリックされた対応する位置のパネルが返されます.

地雷(「M」)が掘り出されるとゲームは終了する-それを「X」に変更する.

隣接地雷のない空のブロック(‘E’)が掘り出された場合、それを(‘B’)に修正し、隣接するすべての掘り出されていないブロックが再帰的に暴露されるべきである.

少なくとも1つの地雷に隣接する空のブロック(「E」)が掘り出された場合、隣接する地雷の数を表す数字(「1」~「8」)に変更される.

今回のクリックで、より多くのブロックが露出されなければ、パネルに戻ります.

例1:

  : 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

  : 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

例2:

  : 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

  : 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

注意:

入力行列の幅と高さの範囲は[1,50]である.

クリックの位置は、掘り出されていないブロック(「M」または「E」)のみであり、これは、パネルが少なくとも1つのクリック可能なブロックを含むことを意味する.

入力パネルは、ゲームが終了した状態ではありません(つまり、地雷が掘り出されています).

単純化のために、言及されていない規則は、この問題において無視され得る.例えば、ゲームが終わると、すべての地雷を掘り出す必要はありません.ゲームやマークボックスを勝ち取る可能性があることを考慮します.

構想
DFS

1.       ，     X   
2.        :
	         ：
	1.     B，        (           E，       )
	2.       

時間複雑度:O(m*n)空間複雑度:O(m*n)
Python 3コード

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        #       ，     X   
        if board[click[0]][click[1]] == 'M':
            board[click[0]][click[1]] = 'X'
            return board
        
        self.m, self.n = len(board), len(board[0])
        direction = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (-1, -1), (1, -1))

        #         
        def check(i, j):
            cnt = 0
            for x, y in direction:
                x, y = x + i, y + j
                if 0 <= x < self.m and 0 <= y < self.n and board[x][y] == 'M':
                    cnt += 1
            return cnt
        
        # DFS
        def dfs(i ,j):
            cnt = check(i, j)
            #      
            if not cnt:
                board[i][j] = 'B'
                for x, y in direction:
                    x, y = x + i, y + j
                    if 0 <= x < self.m and 0 <= y < self.n and board[x][y] == 'E':
                        dfs(x, y)
            #       
            else:
                board[i][j] = str(cnt)

        dfs(click[0], click[1])
        return board

GitHubリンク
Python