yukicoder - No.585 工夫のないパズル
https://yukicoder.me/problems/no/585
コンテスト中、A 問題を通した後ずっとこれを実装していて、結局間に合わず 1 完になった。でも ★4 AC は嬉しい。
概要
4 × 4 のスライドパズルを解く問題。いわゆる 15 パズル と似ているが、空きマスがない代わりに行か列を一つ選んでスライドすることができるというルール。右か下に任意マス分スライドするのを 1 回として、100 回以内の自由な操作で揃えればよい。
解説
おもむろに実験すると、最初の $3$ 行 (列でもいいけれど) は簡単にできそうということが分かる。後々の実装を楽にするために整理しておこう。
$i$ 行目 (0-indexed) までが揃っているとして ($0$ 行目は $-1$ 行目まで揃っていると考える)、次の $i + 1$ 行目を $i$ 行目までを崩さず揃えるには、基本的に下のようにすればよい。
今注目している移動させたい数字のマスの初期座標を $(sr, sc)$、移動先を $(tr, tc)$ とし (ただし、$(行, 列)$)、$round(i) = (i \% 4 + 4) \% 4$ とすると、
基本操作
- 列 $tc$ を $sr - tr$ 下へスライド
- 行 $sr$ を $round(tc - sc)$ 右へスライド
- 列 $tc$ を $4 - (sr - tr)$ 下へスライド
ここでは、アルファベットの代わりに 0-15 の数字を使うことにする。今興味がない数字は省略。
ヤバそうなケースもしっかり考えておく。例えば、移動元と移動先が同じ行にある場合は、次のようにする。
移動元と移動先の行が同じ場合 ($sr = tr$)
- 列 $sc$ を $1$ 下へスライド
- 列 $tc$ を $1$ 下へスライド
- 行 $sr + 1 (= tr + 1)$ を $round(tc - sc)$ 右へスライド
- 列 $sc$ を $3$ 下へスライド
- 列 $tc$ を $3$ 下へスライド
移動元と移動先が同じ列にある場合は、右へずらしてあげるとよい。
移動元と移動先の列が同じ場合 ($sc = tc$)
- 行 $sr$ を $1$ 右へスライド
- 基本操作 ($sc$ の値を更新しておくこと)
以上の操作で、最初の $3$ 行を揃えることができる。
さて、最後の行を適当に入れ替えたい。簡単のために、隣り合うマスを交換する操作のみを考える。結論から言うと、次の操作で可能。
$r = sr (= tr)$、$c = round(sc + 1)$ とすると、
隣り合うマスの交換
- 列 $c$ を下へ $1$ スライド
- 行 $r$ を右へ $1$ スライド
- 列 $c$ を下へ $3$ スライド
- 行 $r$ を右へ $2$ スライド
- 列 $c$ を下へ $1$ スライド
- 行 $r$ を右へ $1$ スライド
- 列 $c$ を下へ $3$ スライド
- 行 $r$ を右へ $1$ スライド
この操作によって、自明に列のマスを任意の順番に並べ替えることができるため、以上の考察ですべてのマスを揃えることができた。
ちなみに 適当にググって出てきたページ にも同じようなことが書いてある。
操作の回数については、以上の解法をそのまま実装すると少しギリギリだが、最適化の余地は十分にあるので、いい感じにえいすれば比較的余裕だと思われる。
