古典的な "ブロックバスター"への解決

Question

英国では80年代から90年代にかけて（70年代も信じていました！）、このようなハニカムグリッドに六角形の表示を持った "ブロックバスター"という古典的なテレビ番組がありましたぼやけPIC用）：！あなたが見ることができるように

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

、文字の5列と4行があります。 1人の人やチームが水平に旅行しようとしている、1人が垂直に旅行しようとしています。あなたは質問に答えることによって六角形に勝つと、答えはその六角形に表示された文字で始まります。

優勝者またはチームが最初に「ラインをつなぐ」 - それはそれ自体に戻る可能性があります（たとえば、その六角形を獲得した相手チームによってブロックされている場合など）。組み合わせ。

私はちょうどコーディングを始めたとき、私はこのパズルに基づいて会議のゲームを作った（著作権侵害を避けるために八角形と四角で交互に作った）が、私はいつも苦労したビットはチェックするアルゴリズムだった完全な行が作られたとき。簡単なものは大丈夫ですが、上がったり、下ったり、前後したりするものがあります。

私は基本的にすべての事実を捕まえなかった巨大なブルートフォースループをコーディングしました。したがって、ロジックがそれを検出しなかった場合、すぐに勝者を宣言できるように、会議主催者の画面にボタンを置く必要がありました。汚いハックについて話してください...

私は解決しなければならなかったこのパズルに戻って考えると、あなたのうちの誰かがより洗練されたソリューションを提案してくれると思いますか？もちろん、言語にとらわれない（擬似コードはすべて喜んで受け入れられる）。

を編集してください。データを保存しても問題ありません。私はそれを配列に貼り付けた。

Answer 1

Flood fillと呼ばれる簡単なグラフィックスアルゴリズムがこれを行うことができます。

これは単純なマルチパスのアプローチでも行うことができます。ブロックバスターボードは非常に小さく、各セルを何度も訪れてもパフォーマンスに大きな影響はないと私は考えています。アプローチを最初に試してください：

すべてのセルをループします。セルがプレーヤによって所有されていて、このフィルルーチンによって「マークされた」セルに6辺がある場合、そのセルに隣接している場合、セルもマークされます。再度すべてのセルをループし、現在のプレーヤーにセルがマークされなくなるまで再度ループします。ここではいくつかの擬似コードです：ボードの適切な側のセルのいずれかがプレイヤーに属している場合、この時点で

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

問題は、2つのノードがグラフで接続されているかどうかを変換します。

• ボードは、無向グラフで見ることができます。ノードはセルであり、隣接するセルであればエッジがあります。
• 側面もグラフのノードであり、それらは、それらに隣接するセルへのエッジを持っている
• （そのプレイヤーのためにチェックした場合に上部と下部を含む）は、使用できるノード
• チェックのサブグラフを取ります上部と下部がDFSを使用して接続されている場合

Answer 3

トリックは、各ブロックに座標を割り当てることです。これは、奇数を相殺するために、描画アルゴリズムの責任です0から3

に何ができるのxとシンプルな4×4の正方形のグリッドと考えるが、4の範囲0座標であり、Y

六角形の半径の半分を下にしてxセル（1と3）をぴったりとはめ込むようにします。

各セルについてisAdjacent(other)メソッドを考えてみましょう。正方形のグリッドでは、単純なチェックをしてisAdjacentを推論することができます：if self.x == other.x＆plusnn; 1とself.x == other.x＆plusnn; 1.検査するyには、x、-1、0,1の-1、0,1の8つの関連する組み合わせがある。

六角形のグリッドでは、隣接関係は少し異なります。もしself.y == other.y＆plusnn; 1とself.x == other.xはその一部です。しかし、xの隣接関係は、どの列が自己であるかによって決まります。xが偶数列（0、2、4）の場合、隣接セルは奇数列にあり、self.y == other.yまたはself.y == other.y + 1同様に、xが奇数列（1,3）である場合、隣接セルは偶数列になります。私はそれをあなたに残して、残りの部分を取り上げてくれるでしょう。

「エッジについて」簡単です。あなたのgrid.get()メソッドにそれらを含めてください。範囲外座標の場合、決して占有されない特殊なダミーセルを返します。これは、比較を簡単にします。

いいえ、与えられたisAdjacent()どのように水平または垂直の接続されたパスを見つけるには？

実際には、列挙型の2つの形式が隣接している必要があります。 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が奇数列にある場合は2つの値、つまり(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のリスト内の隣接するセルを見つけます。