3

すべてのテトロミノのリストを生成するにはどうすればよいですか? または、より一般的には、セルの数に制限されたポリオミノのサブセットを生成するにはどうすればよいですか?

4

3 に答える 3

5

これを行うには多くの方法があります。私がうまく機能することがわかったオプションの 1 つは、再帰的に、より一般的に考えることです。特に：

  1. 1 つの長方形は 1-omino です。
  2. 任意の n オミノの場合、n オミノの任意のブロックにブロックを隣接させることで、(n+1) オミノを作成できます。

これにより、可能なすべての n-omino をリストする再帰的な方法が得られます。ただし、これにより同じ n-omino の複数の回転と平行移動が生成されるため、注意が必要です。これを修正するには、参照座標系を選択し、n-omino を変換して、常にその座標系の軸と同じ高さになるようにします。それが機能したら、結果のn-ominoを軸を中心に回転させ、それを標準位置に戻すだけで、すべての回転を生成できます。

于 2011-01-24T04:05:53.117 に答える
2

N-omino に必要な最大のグリッドは NxN です。すべてを生成してから、回転と平行移動を除外します。

これは、N-1 ステップのパス フォローイング アルゴリズムと考えることができます。グリッドの左上のセルから開始し、そこから右または下にのみ移動すると、ほとんどの平行移動と回転を回避できます。私が間違っていなければ、残るのは同形の N オミノネだけです。例えば、Right-Down-Left のパスによって作成されるテトロミノは、Down-Right-Up と同じです。

于 2011-01-24T04:04:56.863 に答える
1

テトロミノは形です。コンピュータは形状を直接表現するのではなく、数値をバイナリ信号として表現します。プログラマーは、形状を数値として表現する方法を決定します。ビットマップ、文字列、列挙型として保存できます...

特定のヘルプが必要な場合は、より明確な質問を作成する必要があります。

また、7 つの既知の不変の形状のリストを生成する理由にも興味があります。Tetris ゲームを作成している場合、これらの 7 つの形状を変数、定数、または画像としてどこかにハードコーディングし、それらを生成しません。

于 2011-01-24T04:01:26.780 に答える