3

80年代から90年代にかけての英国（70年代もそうだと思います！）には、「ブロックバスター」と呼ばれる古典的なテレビ番組がありました。

古い大ヒットテレビゲームからの写真
（出典：ukgameshows.com）

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

勝った人またはチームが最初に「ラインを接続」します-それはそれ自体に戻る可能性があることに注意してください（たとえば、その六角形を勝ち取った相手チームによってブロックされた場合）、多くの可能な勝ちの組み合わせがあります。

数年前、コーディングを始めたばかりのとき、このパズルに基づいて会議ゲームを作成しました（著作権侵害を避けるために八角形と正方形を交互に作成しました！）が、私がいつも苦労したのは、完全な行がいつになるかをチェックするアルゴリズムでした作られた。簡単なものでも大丈夫ですが、上下左右に行き詰まってしまいました！

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

今、私が解決しなければならなかったこのパズルを振り返ると、そこにいる誰かがもっとエレガントな解決策を提案したいと思うだろうか？もちろん言語に依存しません（すべて、喜んで受け入れられる擬似コードを含みます）。

編集データを好きなように保存するのは問題ありません。アレイに貼り付けました。

4

3 に答える 3

8

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

これは、単純なマルチパスアプローチでも実行できます。大ヒットボードは非常に小さいため、各セルに何度もアクセスしても、パフォーマンスに目立った影響はまったくないと思います。したがって、このアプローチを最初に試すことをお勧めします。 ：

プレーヤーごとに、すべてのセルをループします。セルがプレーヤーによって所有されており、この塗りつぶしルーチンによって「マーク」されたセルの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!!

この時点で、ボードの適切な側のセルのいずれかがプレーヤーに属している場合、プレーヤーはボードのその側に到達しました。

于 2009-08-25T09:39:15.100 に答える
1

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

  • ボードは無向の「グラフ」として見ることができます。ノードはセルであり、隣接するセルの場合はエッジがあります。
  • 辺もグラフのノードであり、隣接するセルにエッジがあります。
  • 使用できるノードのサブグラフを取ります（そのプレーヤーをチェックする場合は上と下を含む）
  • 上部と下部がDFSを使用して接続されているかどうかを確認します
于 2009-08-25T10:03:34.803 に答える
1

秘訣は、各ブロックに座標を割り当てることです。

できることは、x座標が0から4の範囲で、yが0から3の範囲にある単純な4x4の正方形グリッドと考えることです。

奇数のxセル（1と3）を六角形の半径の半分だけオフセットして、適切にフィットさせるのは、描画アルゴリズムの責任です。

isAdjacent(other)各セルの方法を考えてください。正方形のグリッドでは、簡単なチェックでisAdjacentを推論できます。self.x==other.x±1およびself.x== other.x±1の場合、-1、0、1の8つの関連する組み合わせがあります。チェックするyの場合はx、-1、0、1の場合。

六角形のグリッドでは、隣接関係は少し異なります。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()水平または垂直の接続されたパスを見つける方法を考えれば？

実際には、2つの形式の列挙を隣接させたいと考えています。作成したいenum_adjacent_vert(y_offset)とenum_adjacent_horiz(x_offset)。垂直方向に隣接するものを列挙するには、3つの値を生成します(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リストに隣接するセルがあります。

于 2009-08-25T10:24:14.650 に答える