经典"百视达"的解决方案

Question

在整个80年代和90年代的英国(我相信也是70年代!)有一个名为"Blockbuster"的经典电视节目,它在蜂窝网格中显示六边形,就像这样(对于模糊的照片抱歉!):

来自老百视达电视游戏的图片http://www.ukgameshows.com/atoz/programmes/b/blockbusters/blockbusters_panel.jpg

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

获胜的人或团队是第一个"连接一条线" - 注意,这可能会自行回归(例如,如果它被赢得那个六边形的对方球队阻挡),那么有很多很多可能的获胜组合.

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

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

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

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

Answer 1

一个简单的图形算法称为Flood填充可以做到这一点.

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

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

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

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