algorithm - 经典 "Blockbuster"的解决方法

Question

在整个 80 年代和 90 年代(我相信也是 70 年代!)的英国，有一个名为“Blockbuster”的经典电视节目，其中显示了蜂窝网格中的六边形，如下所示(抱歉图片模糊!):

_{(来源:ukgameshows.com)}

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

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

几年前，当我刚开始编码时，我基于这个谜题写了一个 session 游戏(我们让它交替出现八边形和正方形以避免侵犯版权!)但我一直纠结的一点是检查何时的算法完成了一条完整的生产线。简单的没问题，但我真的卡在了上、下、来回的问题上!

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

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

编辑 以您想要的方式存储您的数据是可以的。我把它放在一个数组中。

Answer 1

一种名为 Flood fill 的简单图形算法可以做到这一点。

它也可以通过简单的多 channel 方法来完成——blockbuster board 太小了，我认为多次访问每个单元根本不会对性能产生任何明显的影响——所以我提倡这种方法先试用:

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

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

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