3

在整个 80 年代和 90 年代的英国（我相信也是 70 年代！）有一个经典的电视节目叫做“大片”，它在蜂窝网格中显示六边形，像这样（抱歉图片模糊！）：

图片来自旧版 Blockbuster 电视游戏
（来源：ukgameshows.com）

如您所见，有 5 列字母和 4 行。1个人或团队正在尝试水平旅行，一个人正在尝试垂直旅行。您通过回答一个问题赢得一个六边形，答案将以该六边形中显示的字母开头。

获胜的人或团队是第一个“连接线”的人 - 请注意，这可能会自行返回（例如，如果它被赢得该六边形的对方团队阻挡）因此有很多很多可能的获胜组合。

几年前，当我刚开始编码时，我根据这个谜题编写了一个会议游戏（我们让它交替使用八边形和正方形以避免侵犯版权！）但我一直在努力解决的问题是检查何时完成一行的算法被制作了。简单的很好，但是那些上下，来回的我真的被卡住了！

我最终基本上编写了一个巨大的蛮力循环，但仍然没有捕捉到所有的可能性。因此，我不得不在会议组织者的屏幕上放置一个按钮，以使他们能够在逻辑未检测到它的情况下快速宣布获胜者！谈论肮脏的黑客...

现在我回想起我必须解决的这个难题，我想知道你们中是否有人愿意提出一个更优雅的解决方案？当然语言不可知论（所有包括愉快地接受的伪代码）。

编辑您可以按照自己的方式存储数据。我把它放在一个数组中。

4

3 回答 3

8

一种称为洪水填充的简单图形算法可以做到这一点。

它也可以通过简单的多通道方法来完成——大片板是如此之小，以至于我认为多次访问每个单元不会对性能产生任何明显的影响——所以我建议先尝试这种方法：

对于每个玩家，循环遍历所有单元格；如果该单元格归玩家所有，并且如果该单元格与此填充例程“标记”的单元格有六个边相邻，则该单元格也会被标记。再次循环遍历所有单元格，直到没有单元格被标记为当前玩家。这是一些伪代码：

for player in players:
  # those on the starting edge that the player owns get 'marked'
  for cells in cells.start_edge(player):
    if cell.owner = player:
      cell.mark = player
  do:
    count = 0
    for cell in cells:
      if cell.mark == None && cell.owner == player:
        for adjacent in cell.neighbours:
          if adjacent.mark == player
            cell.owner = player
            count += 1
            break
  while count
  for cell in cells.stop_edge(player):
     if cell.mark == player
       player won!!

此时，如果棋盘适当一侧的任何单元格属于玩家，则玩家到达棋盘的那一侧。

于 2009-08-25T09:39:15.100 回答
1

诀窍是为每个块分配坐标。

您可以将其视为一个简单的 4x4 方形网格，其中 x 坐标在 0 到 4 范围内，y 在 0 到 3 范围内。

绘图算法负责将奇数 x 单元格（1 和 3）向下偏移六边形半径的一半，以便它们正确地组合在一起。

为每个单元考虑一种isAdjacent(other)方法。在方形网格中，您可以通过简单的检查来推断 isAdjacent：if self.x == other.x ± 1 和 self.x == other.x ± 1。-1、0、1 有 8 种相关组合对于 x, -1, 0, 1 对 y 进行检查。

在六边形网格中，邻接有点不同。如果 self.y == other.y ± 1 和 self.x == other.x 是其中的一部分。但是x邻接取决于self在哪一列。如果x是偶数列（0,2,4），那么相邻单元格在奇数列，也就是说self.y == other.y or self.y == other.y + 1。类似地，如果 x 是奇数列 (1, 3)，则相邻单元格在偶数列中。剩下的 isAdjacent 就交给你了。

“边缘呢”？简单的。将它们包含在您的grid.get()方法中。对于越界坐标返回一个从未被占用的特殊虚拟单元。它使比较更简单。

好的，鉴于isAdjacent()我如何找到水平或垂直的连接路径？

实际上，您需要两种相邻的枚举形式。您想要创建enum_adjacent_vert(y_offset)和enum_adjacent_horiz(x_offset). 枚举垂直相邻的产量三个值(self.x-1, self.y+y_offset), (self.x, self.y+y_offset), (self.x+1, self.y+y_offset)。要枚举水平相邻的，如果 self.x 在奇数列中，则产生两个值：(self.x+x_offset, self.y), (self.x+x_offset, self.y+1)。如果 self.x 在偶数列中： (self.x+x_offset, self.y), (self.x+x_offset, self.y-1).

这是相对直截了当的。给定一个边缘单元，您想在特定方向上“穿过”或“向下”板到相邻单元。

假设您从左到右（增加 x）。您想在enum_adjacent_horiz列表中找到相邻的单元格。要从上到下（增加 y），您会在enum_adjancent_vert列表中找到一个相邻的单元格。

于 2009-08-25T10:24:14.650 回答
1

您的问题转化为两个节点是否在图中连接。

  • 您可以将董事会视为无向的“图表”。节点是单元格，如果它们是相邻的单元格，则它们具有边。
  • 边也是图中的节点，它们与相邻的单元格有边
  • 获取您可以使用的节点的子图（如果检查该播放器，则包括顶部和底部）
  • 检查顶部和底部是否使用 DFS 连接
于 2009-08-25T10:03:34.803 回答