经典“百视达”的解决方案

Question

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

（来源：ukgameshows.com）

如您所见，有5列字母和4行。 1个人或团队试图横向移动，一个人试图垂直移动。你通过回答问题赢得六角形，答案将从六角形中显示的字母开始。

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

多年前，当我刚刚开始编码时，我写了一个基于这个谜题的会议游戏（我们制作了交替的八边形和正方形，以避免版权侵权！）但我一直在努力的是检查完整线路的算法成了。简单的很好，但是上下，来回上下我真的被困住了！

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

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

编辑可以按照您的需要存储数据。我把它放在一个数组中。

Answer 1

一个简单的图形算法叫做Flood fill就可以做到这一点。

它也可以通过一个简单的多通道方法完成 - 重磅炸弹板非常小，我不认为多次访问每个单元会对性能有任何明显的影响 - 所以我主张先尝试这种方法：

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

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!!

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

Answer 2

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

您可以做的是将其视为一个简单的4x4方格，x坐标的范围为0到4，y为0到3。

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

想想每个细胞的isAdjacent(other)方法。在正方形网格中，您可以通过一个简单的检查推断出相邻：如果self.x == other.x±1和self.x == other.x±1。有8个相关的组合-1,0,1对于x，-1,0,1，要检查y。

在六边形网格中，邻接有点不同。如果self.y == other.y±1和self.x == other.x是其中的一部分。但x邻接取决于self所在的列。如果x是偶数列（0,2,4），则相邻单元格在奇数列中，这意味着self.y == other.y或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列表中找到相邻的单元格。

Answer 3

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

• 您可以将电路板视为非定向“图形”。节点是单元格，如果它们是相邻单元格，则它们具有边缘。
• 边也是图中的节点，并且它们具有与它们相邻的单元的边
• 获取您可以使用的节点的子图（如果检查该播放器，则包括顶部和底部）
• 检查顶部和底部是否使用DFS连接