扫雷者算法，从起始方开始打开所有相互接触的安全方格

Question

我正在驾驶一艘扫雷艇，我必须做一个功能，可以查看起始广场周围的所有广场。然后，它应该打开这些方块，并在新打开的方块周围不断检查，直到没有更多的安全方块与安全方块接触。到目前为止，我所拥有的是

safe = [(x, y)]
while safe != []:
    k, c = safe.pop(-1)
    field[c][k] = "1"
    for i in range(k - 1, k + 2):
        for j in range(c - 1, c  + 2):
            if 0 <= i < len(field[0]) and 0 <= j < len(field):
                if field[j][i] == "1":
                    pass
                elif field[j][i] != "x":    
                    field[j][i] = "1"
                    safe.append((i, j))

这确实会打开方块，但它也会打开对角接触的方块，给我一个结果，比如

我使用的字段是这个

field = [
[" ", " ", " ", "x", " ", " ", " ", " ", " ", " ", " ", "x", " "], 
[" ", " ", "x", "x", " ", " ", " ", "x", " ", " ", " ", "x", " "], 
[" ", "x", "x", " ", " ", " ", " ", "x", " ", " ", "x", "x", " "], 
["x", "x", "x", "x", "x", " ", " ", "x", " ", "x", " ", " ", " "], 
["x", "x", "x", "x", " ", " ", " ", " ", "x", " ", "x", " ", " "], 
[" ", " ", "x", " ", " ", " ", " ", " ", " ", "x", " ", " ", " "]]

我该怎么做才能阻止这种情况发生？另外，我知道安全方块都标记为1，但这是一个额外的过程，这将帮助我以后完全编码游戏，所以它并不意味着给出正确的地雷数量

Answer 1

您的代码正在板上所有8个周围的“tile”上迭代，而您只需要检查4个tile（1个在上面，1个在下面，1个在左边，1个在右边）。这是一个基本的洪水填充算法。您应该使用一个循环，而不是使用两个循环，以及一个包含位置/移动的列表，如Nico Schertler所评论的。以下是固定代码：

safe = [(x, y)]
moves = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while safe != []:
  k, c = safe.pop(-1)
  field[c][k] = "1"
  for i in moves:
    if 0 <= i[0]+k < len(field[0]) and 0 <= i[1]+c < len(field):
      if field[i[1]+c][i[0]+k] == "1":
        pass
      elif field[i[1]+c][i[0]+k] != "x":    
        field[i[1]+c][i[0]+k] = "1"
        safe.append((i[0]+k, i[1]+c))

我希望这是清楚的。通过搜索，您总是可以了解有关洪水填充算法的更多信息