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

Question

我正在编写一个扫雷器，我必须创建一个函数来查看起始方 block 周围的所有方 block 。然后它应该打开这些方 block 并不断检查新打开的方 block 周围，直到没有更多的安全方 block 与安全方 block 接触。到目前为止我所拥有的是

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", " ", " ", " "]]

我应该怎么做才能阻止这种情况发生？我也知道安全方 block 都标记为 1，但这是类(class)中的练习，可以帮助我稍后完整地编写游戏代码，所以它还不意味着给出正确数量的地雷。

Answer 1

当您应该只检查 4 个图 block (上面 1 个，下面 1 个，左边 1 个，右边 1 个)时，您的代码正在遍历棋盘上所有 8 个周围的“图 block ”。这是一个基本的洪水填充算法。你应该使用一个循环而不是你使用的 2 个循环和一个包含位置/移动的列表，就像 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))

我希望它是清楚的。您随时可以通过搜索了解更多关于洪水填充算法的信息。