扫雷代码打开没有最大递归深度的零框

Question

我正在 Python 制作扫雷。我已经完成并运行了所有代码，但我想添加的一个功能是，当您打开附近有零个地雷的图块时，它会打开它周围的所有方块。问题源于这样一个事实，即如果我打开的任何盒子也为零，他们也需要打开它们周围的所有盒子。我相信我有执行此操作的功能，但始终会达到最大递归深度。我尝试将限制提高到可能高于我应有的水平，但我仍然遇到错误。我想知道他们是否是在没有这么多递归的情况下执行此操作的不同方法。感谢您的帮助，这是我当前的代码：

def open_zero(x):
    # For opening the boxes with no nearby mines
    # First, opens the box the user clicked on
    button_list[x].config(bg="#90949b")
    # Then opens all nearby boxes through the box_open function
    # I need to run these values through the function so that if they are
    # zero, they will open all nearby tiles as well.
    # This causes too much recursion.
    box_open(x+1)
    box_open(x-1)
    box_open(x+width)
    box_open(x+width+1)
    box_open(x+width-1)
    box_open(x-width)
    box_open(x-width-1)
    box_open(x-width+1)

  def box_open(x):
      if box_list[x] == "M":
          # Checks if the block is a mine
          button_list[x].config(image=photo_mine, relief = SUNKEN)
          # Stops if it was a mine
          button_frame.destroy()
          all_code()
      elif box_list[x] == 0:
          # If there are no nearby mines, open all nearby tiles.
          open_zero(x)
      else:
          # If not a mine, change button text to the amount of nearby mines.
          button_list[x].config(text=box_list[x], bg="#90949b")

希望您能从这段代码中理解我的代码。按照我的编码方式可能不太可能，但如果有人有任何想法，我很乐意听取他们的意见。感谢您的帮助！

Answer 1

您可以使用 queue。在 Python 中，这可能以 list 的形式出现。使用 .append() 使项目入队，使用 .pop() 使项目出队。（请注意，您不需要使用队列。您可以使用堆栈或普通列表，但队列会模拟单元格从点击的中心展开，如果您想要一些简洁的动画，这可能会有所帮助。）

##  TODO check over this implementation
def is_open(x):
    return button_list[x].bg == "#90949b"


def open_zero(x):
    button_list[x].config(bg="#90949b")

    queue = [x]                     ##  init

    while queue:
        curr = queue.pop(0)         ##  dequeue cells here

        if is_open(curr):           ##  STOPPING CONDITION    [1]
            continue

        box_open(curr)

        if box_list[curr] != 0:     ##  checks if curr is a zero-cell, you've already implemented this previously 
            continue


        ##  enqueue nearby cells here

        # if curr >= width:         ##  STOPPING CONDITION(s) [2]
        queue.append(curr+1)        ##  TODO check curr isn't on the right edge
        queue.append(curr-1)        ##  TODO check curr isn't on the left edge
        queue.append(curr+width)    ##  TODO check curr isn't on the bottom edge
        queue.append(curr+width-1)  ##  ... 
        queue.append(curr+width+1)  ##  ... the rest has been left as an
        queue.append(curr-width)    ##  ... exercise for the reader
        queue.append(curr-width-1)
        queue.append(curr-width+1)

        ##  NOTE: without STOPPING CONDITION(s), recursion or the while-loop
        ##  will never terminate
        ##  except for the max-recursion depth

请注意，Python 对代码中的递归感到不满的一个原因是您没有提供任何 stopping 或 终止条件。我无法强调这些有多重要。我已经部分实现了其中一个条件（is_open(x)，它检查单元格 x 是否打开）。

由于这是扫雷，我假设您是在 matrix/grid 上制作的（但将按钮存储在列表中）。尽管如此，您仍需要检查网格的边界，否则您的递归将跳过网格墙或做其他奇怪的事情。

（思想实验：假设我点击网格左下角的单元格。这将触发 box_open(x)。这将依次触发 box_open(x-1) 或 queue.append(curr-1)...但是这些将打开倒数第二行最右边的单元格。这是意外的。您需要检查该单元格是否不在左边缘。 .. 在做 box_open(x-1).)

之前

我非常相信您的原始代码可以工作，但递归（或任何循环）的重要关键要素之一是提供stopping/terminating 条件。这应该是每个人在这里的主要收获（除了队列的实现）。

扫雷代码打开没有最大递归深度的零框

Minesweeper code opening the zero boxes without max recursion depth

python

recursion

minesweeper