算法搜索扫雷艇中的空单元格

Question

我创建扫雷艇，只是想知道当用户按下空单元格时搜索所有空单元格的最佳算法，然后增长并限制到边界直到它到达炸弹单元格。我计划使用递归搜索，但可能会减慢这个过程。

谢谢。

Answer 1

如果你以图形描绘了检测我会说这将是最好的做多步（正如你提到的增长边界）：

1. 显示的点击广场，找到附近的所有条目这显然是处理。
2. 显示这些方块，找到明显处理的所有条目。从第2步

这样，用户就可以看到这一点这是一件好事

重复。混合一些动画，它可能是一些很酷的东西，让人有希望发生。

Answer 2

Epsilon Prime的解决方案是实施它的好方法。

你可以用队列来做到这一点。

例子：

push the first empty cell/point 
LOOP until queue non empty 
    pop.head cell and reveal it 
    push the empty surrounding cells of it (8 at maximum) 
    (you must flag the cells so you don't push them again, 
     ie dont push the cells that are already revealed) 

Answer 3

从算法的角度来看，你不能去错Breadth-First Search或Depth-First Search。 Nick D's answer基本上描述了广度优先搜索，但一般来说，你想要的解决方案是“当你仍然在看广场，显示广场;如果广场没有炸弹邻居，那么对于它的八个邻居中的每一个尚未访问过，请将它们标记为已访问并将它们添加到您正在查看的广场列表中“。重复，直到你正在看的广场清单是空的，并从用户点击的方块开始。