データ構造を考える (KATAMINOを解くプログラムを作成する)

★前回の記事

yucatio.hatenablog.com

具体的なプログラミングに入る前に、データ構造を考えておきましょう。

KATAMINOを解くのに必要なものは、KATAMINOを入れるフィールドとKATAMINOのピースです。

フィールドのデータ構造

フィールドは 5 x {ピースの数} のマス目です。

f:id:yucatio:20190619224647p:plain:w250

これは2次元配列で表現できそうです。 まだピースが置かれていない場所は-1にしておきます。フィールドの幅が3つの時は以下のようになります。

[
  [-1, -1, -1],
  [-1, -1, -1],
  [-1, -1, -1],
  [-1, -1, -1],
  [-1, -1, -1]
]

ピースが置かれた場所は、そのピースの番号(ID)で置き換えます。

f:id:yucatio:20190620082653p:plain:w250

上の図のようにピースが置かれたときのデータは以下のようになります。(このT字のピースのIDは9です)

[
  [ 9,  9,  9],
  [-1,  9, -1],
  [-1,  9, -1],
  [-1, -1, -1],
  [-1, -1, -1]
]

以上がフィールドのデータ構造です。

ピースのデータ構造

ピースの表現のしかたは、2次元配列とピースのある場所のリストの2パターン考えられます。

例えば、このピースの場合

f:id:yucatio:20190620083647p:plain:w250

このピースを2次元配列で表現すると以下のようになります。ピースの場所を1, ピースでない場所を0で表現しています。

[
  [1, 1, 0],
  [0, 1, 0],
  [0, 1, 1]
]

リストで表現する場合は、上記の配列のピースの場所のみを抜き出して配列にします。

f:id:yucatio:20190620084008p:plain:w250

[
  {x:0, y:0},
  {x:0, y:1},
  {x:1, y:1},
  {x:2, y:1},
  {x:2, y:2}
]

2次元配列でも埋まっている場所のリストでも解くことはできますが、 ピースを置いたり、重なっている部分の判定がリストの方が効率よくできるので、今回はリストを採用します。

以上がピースのデータ構造です。


★次回の記事

yucatio.hatenablog.com

★目次

yucatio.hatenablog.com