解決經典的「重磅炸彈」

Question

在英國整個80年代和90年代（70年代過於相信！）有一個叫「重磅炸彈」的經典電視節目，其中有六邊形的顯示在蜂窩網格，像這樣（對不起對於模糊PIC）：

picture from old Blockbuster TV game http://www.ukgameshows.com/atoz/programmes/b/blockbusters/blockbusters_panel.jpg

正如你所看到的，有書5列和四行。 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

您的問題轉化爲圖形中是否連接了兩個節點。

• 您可以將電路板視爲非定向的「圖形」。節點是細胞，如果它們是相鄰的細胞，則它們具有邊緣。
• 雙方都在圖還節點，而那些具有邊到與之相鄰的細胞
• 帶您可以使用節點（包括頂部和底部，如果檢查該播放器）
• 檢查的子圖如果頂部和底部連接使用DFS

Answer 3

技巧是爲每個塊分配座標。

你可以做的是把它看成是一個簡單的4x4正方形格子X的取值範圍爲0〜4和y從0到3

協調它的繪圖算法，以抵消奇數的責任編號爲x的細胞（1和3）沿六角形半徑的一半向下，以便它們適當地配合在一起。

想想每個單元的isAdjacent(other)方法。在一個正方形網格中，你可以通過一個簡單的檢查來推理出相鄰：if self.x == other.x＆plusmn; 1和self.x == other.x＆plusmn; 1.對於x，-1，0，1有8個相關的組合，用於檢查y。

在六邊形網格中，鄰接有點不同。如果self.y == other.y + 1和self.x == other.x是它的一部分。但是，x鄰接取決於哪個列自身。如果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列表中找到相鄰的單元格。