3

私は、異なる色の正方形のタイルを自由に組み合わせることができる 8x8 の正方形のボードを持っています。これらの正方形のタイルはさまざまなサイズにすることができ、1 から 8 までの範囲の正方形の辺を持つことができます。ボードのサイズによる最大値は 8 です。

同じ色の正方形の領域を、領域自体と同じ大きさの正方形のタイルに置き換えることができるアルゴリズムを見つける必要があります。

以下の例を参照してください。

例を見るにはここをクリック

これらの例では、より大きな正方形の黄色の領域を取得するために、「x」でマークされたタイルの色を黄色に変更しています。大きな黄色の正方形の領域を、領域自体と同じサイズの対応するタイルに置き換えるアルゴリズムを探しています (ステップ C)。おそらく、アルゴリズムは、色を変更したタイル (「x」でマークされたタイル) から隣接するタイルのチェックを開始できます。

4

1 に答える 1

2

このような小さなボードでは、おそらくブルート フォースを使用できます。このように、可能な正方形をサイズの降順で繰り返します。

for (int width = 8; width > 0; width--) {
    for (int x0 = 0; x0 <= 8 - width; x0++) {
        for (int y0 = 0; y0 <= 8 - width; y0++) {
            int x1 = x0 + width;
            int y1 = y0 + width;
            ...
        }
    }
}

既存の正方形 S ごとに、候補の正方形[x0, x1] * [y0, y1]が S と交差するかどうか、交差する場合は S を含むかどうかをテストします。S が交差するが含まれていない場合[x0, x1] * [y0, y1]は、可能な置換ではありません。S が含まれているが色が間違っている場合も同様です。

候補がこれらのテストに耐えた場合 (元のボードに必要以上のタイルがある場合に変更された正方形が含まれている場合)、それが配置され、含まれている正方形が削除されます。

于 2013-07-14T22:22:10.010 に答える