0

我正在执行一个大小为 7 x 7 的棋盘游戏，w = 白子，b = 黑子。我想计算最终结果。请记住，这是一个虚构的围棋游戏，我们只计算被黑色或白色棋子包围的空单元格。

 0 1 2 3 4 5 6
0    b
1    b w  
2b b w   w
3  w       w
4    w     w
5      w w w
6

我想计算由 w 和 b 包围的所有交叉点，这意味着我想计算白色石头和 0,0 0,1 1 的单元格 2,3 3,2 3,3 3,4 4,3 4,4， 0 1,1 用于黑色宝石。我想出的所有算法都太复杂了。

我将使用 GNU 汇编器来实现最终的解决方案。我刚开始学习汇编语言，所以我不希望它变得复杂。该算法可以使用循环和数组，但不能使用递归或函数调用。

我想看看线性代数中是否有一个简单的算法来解决这个问题，或者如果你能描述一个不使用递归和函数调用的简单算法，我将不胜感激。

4

2 回答 2

2

洪水填充类型算法可能适用：

  1. 找到第一个未分配的单元格。
  2. 如果单元格是空的，则从它填充填充，在边缘单元格或被占用的单元格处停止。
    1. 对于遇到的第一个被占用的单元格，记录占用者的颜色。
    2. 如果遇到的占用单元格是不同的颜色，请记录涉及的颜色不止一种。
    3. 填充后，如果只遇到一种颜色，则将整个区域标记为属于该颜色。该区域中的空单元格的数量被添加到计数中。
  3. 从步骤 1 开始重复，直到分配了所有单元格。

洪水填充是一种相当标准的算法，例如：

  1. 将起始单元推入堆栈。
  2. 虽然堆栈不为空：
    1. 从中弹出一个单元格。
    2. 如果尚未处理单元格（即在这种情况下未分配）：
      1. 处理它（即在这种情况下查看它的颜色）。
      2. 将其所有邻居推入堆栈。

请注意，对于这些算法，如果电路板被一层不可见的“边缘”单元包围，它会变得更容易。就您的算法而言，边缘单元和占用的单元没有邻居。

见http://en.wikipedia.org/wiki/Flood_fill

于 2012-04-18T05:29:27.460 回答
0

我会尝试一种算法，它沿着由空白空间形成的形状的边缘移动，如下所示：

  1. 从与空白空间相邻的一块开始。
  2. 通过测试所有相邻的空间，沿着由空白空间形成的形状的外边缘移动。
  3. 如果您遇到板的边缘，您可以继续沿着板的边缘行驶。
  4. 如果您在形状的边界上同时遇到黑白棋子，则该形状不属于任何玩家。
  5. 否则，刚刚勾勒出的形状属于拥有所有边框的玩家。

然后，您可以使用这些形状来确定每个玩家拥有的空间数量。

由于这个问题被标记为“作业”，因此需要考虑更多事情：这种情况下的结果是什么，你如何解释它？

 0 1 2 3 4 5 6
0
1  w w w w w w
2  w
3  w   b b b
4  w   b   b
5  w   b b b
6  w
于 2012-04-18T05:34:12.423 回答