(Leetcode)扫雷游戏

Question

这是一个Leetcode问题 -

让我们玩Minesweeper游戏(维基百科!_您将得到一个表示游戏板的2D字符矩阵。'M‘表示未显示的地雷，'E’表示未显示的空方块，'B‘表示没有相邻(上、下、左、右和所有四个对角线)的已显示的空白方块，数字(__1 to 8__)表示与该显示方块相邻的地雷数，最后，'X’表示一个已显示的地雷。现在，考虑到所有未显示的方块(__M或E__)中的下一个单击位置(行和列索引)，根据以下规则显示该位置后返回板-

• 如果一个地雷(M)被发现，那么游戏就结束了--把它改为'X‘。
• 如果一个没有相邻地雷的空方块(E)被显示出来，那么将它更改为一个显示空白(B)，并且它的所有相邻的未显示的方块都应该被递归地显示出来。
• 如果显示至少有一个相邻地雷的空方块(E)，则将其更改为一个数字(__1 to 8__)，表示相邻地雷的数目。
• 当没有更多的方块将被揭示时，返回板。

例1-输入：[‘e’，‘E’，‘e’，‘E’，‘M’，‘E’，‘E’，‘e’，‘E’，‘e’，‘E’]单击：3,0输出：[‘B’，‘1’，‘E’，‘1’，‘B’，‘b’，‘1’，‘M’，‘1’，‘B’，‘b’，‘1’，‘1’，‘1’，‘B’，‘B’，‘B’]解释-

示例2-输入：[‘B’，‘1’，‘E’，‘1’，‘B’，‘b’，‘1’，‘M’，‘1’，‘B’，‘b’，‘1’，‘1’，‘1’，‘B’，‘B’，‘B’]单击：1,2输出：[‘B’，‘1’，‘E’，‘1’，‘B’，‘b’，‘1’，‘X’，‘1’，‘B’，‘b’，‘1’，‘1’，‘1’，‘B’，‘B’，‘B’]解释-

注-

• 输入矩阵的高度和宽度范围为[1,50]__。
• 单击位置将仅为未显示的正方形(__M或E__)，这也意味着输入板至少包含一个可点击的方块。
• 当游戏结束时，输入板不会是一个阶段(一些地雷已经被发现)。
• 为了简单起见，在这个问题上应该忽略没有提到的规则。例如，当游戏结束时，你不需要透露所有未公开的地雷，考虑任何你将赢得游戏或标记任何方块的案例。

这是我对这个挑战的解决方案-

class Solution:

    directions = [(-1, 0), (-1, -1), (-1, 1), (0,-1), (0, 1), (1, -1), (1, 0), (1, 1)]

    def updateBoard(self, board, click):
        """
        :type board: List[List[str]]
        :type click: List[int]
        :rtype: List[List[str]]
        """
        return self.dfs(board, click)

    def dfs(self, board, click):
        stack = [(click[0], click[1])]
        m, n = len(board), len(board[0])
        while stack:
            r, c = stack.pop() # last inserted element

            if board[r][c] == 'M':
                board[r][c] = 'X'
                break

            # check for adjacent mines
            mines = 0
            for i, j in self.directions:
                dr = r + i
                dc = c + j
                if 0 <= dr < m and 0 <= dc < n and board[dr][dc] == 'M':
                    mines += 1
            board[r][c] = str(mines) if mines else 'B'

            # add neighbors
            for i, j in self.directions:
                dr = r + i
                dc = c + j
                if 0 <= dr < m and 0 <= dc < n and board[r][c] == 'B' and board[dr][dc] == 'E':
                    stack.append((dr, dc))

        return board

这是我的代码结果(54个测试用例)-

所以，我想知道我是否能使这个程序更短、更高效。

任何帮助都将不胜感激。

Answer 1

• M字段从不被推送。这种情况可能只是由于不幸的单击而发生的。在循环中测试board[r][c] == 'M'是浪费时间。在循环之前测试一次，if board[click[0]][click[1]] == 'M'。
• 类似地，如果字段不是空的，则不应该麻烦邻居。board[r][c] == 'B'的测试发生得太晚了。作为实现，对于其他字段，代码仍然计算邻居--并且对它们不做任何操作。
• 0 <= dr < m and 0 <= dc < n的测试也可能导致性能问题，而且看起来不像Pythonic。不请求宽恕，例如尝试:如果董事会灾难恢复 == 'M'：+= 1除IndexError: pass
• 相当多的字段被多次推敲和检查。我不确定这是否是一个瓶颈；然而，洪水填充算法的右手和扫描线方法确实值得研究。