SRM651 div1 500

問題

無限に大きなマスのボードが与えられる。
M匹のきつねがいるマスの座標が与えられる。
集まるとは、すべてのきつねがいるマスが隣接しているような状態を指す。
このM匹が集まりたいとき、全員の移動距離の最小値を答える。

M<=6
-10^9<=座標<=10^9

考え方

きつねのx座標、y座標をそれぞれバラバラに見て、それぞれの組み合わせで作れる座標付近に集まることが考えられる。
しかし、座標付近で、どのような形状できつねが集まる場合に移動距離が最小になるかわからない。

これを全探索することを考える。
座標は6*6=36座標が考えられる。
この座標を起点に、再帰的に隣接するようにマスをつなげてM個になるようにマスを作る。
このマスに対して、どのマスにどのきつねを割り当てるかで6!=720通りあり得る。

再帰関数で隣接マスの部分ときつねを割り当てる部分を書くと、重複があり得るので、メモしながら実際に生成してみると隣接マス部分(マスの形状と番号割り当て)は1296通りぐらいしかない模様。
36*1296*720=3.3*10^7ぐらいなので、ギリギリ通る。