C/C++ での数字接続ゲーム?

ゲーム - n × n の正方配列があるとします。その中には、空の正方形、実線の正方形、および非実線の正方形があり、整数 1、2、3、... で設定されます。各整数は、ボード上の 2 つの異なる正方形を保持または占有します。プレイヤーのタスクは、水平方向と垂直方向の動きのみを実装する単純なパスを使用して、ボード上の各整数の 2 つの出現を接続することです。 2 つの異なるパスが交差することはできません。どのパスにもソリッド ブロックを含めることはできません (どのパスにもソリッド ブロックは許可されません)。最後に、すべての非実線の正方形をパスで埋める必要があります。

アルゴリズム - 与えられたボード サイズ n × n で効率的なランダム パズルを構築するには、まず黒板上にランダムで単純な相互に素なパスを生成します。一部の分離されたブロックが生成されたすべてのパスの外側にまだある場合は、これらの分離されたブロックをソリッド (禁止) としてマークします。次に、パスの終点と塗りつぶされた正方形のリストをパズルとして提供します。

したがって、最初に解を生成し、次にその解に基づいてパズルを計算します。パスと実線の正方形は n × n 個のプレートを分離します。このパーティションを生成するためのデータ構造を実装して見つけます。このデータ構造は、チェス盤上の n^2 個の正方形のセットのサブセットを処理します。

疑似コード

• 位置決め正方形 (a、b) および (c、d) がチェス盤上にランダムに表示され、-

  • になります。

    (a, b) と (c, d) は互いに隣接しており、

  • (a, b) と (c, d) は世代の一部ではありません。ここまではどんな道でも。もし入っているなら ボード全体、FAILURE を返します /* ここで、(a, b) と (c, d) は新しいパス上の最初の 2 つの正方形です 確立する。 */

• 以下を含む 2 つの和集合検索ツリーを結合します。 (a、b) および (c、d)。

• 現在のパスを展開できるまで繰り返します -

  (a, b) = (c, d) の名前を変更します。

次のようなランダムに隣接する正方形 (c, d) (a, b) を見つけます。 -

• ( c , d) は、これまでに生成されたどのパスにも属しません (現在のパスを含む)

• 部分的に構築された現在のパス上の唯一の近傍 (c, d) は (a, b) ）。

そのような近傍 (c、d) が見つからない場合、パスをさらに延長することはできないため、サイクルは中断されます。

それ以外の場合は、(a, b) と (c, d) が属する 2 つのツリーを見つけます。

先頭と先頭にある 2 つのブロックのエンドポイント フラグを設定して、新しいパスを終了します。

#成功を返す

以上がC/C++ での数字接続ゲーム?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。