問題概要
$h \times w$ のグリッドがあり，グリッドの各セルには $1$ 以上 $h w$ 以下の整数がそれぞれひとつずつ書き込まれている．
このグリッドに対し，以下の操作を $0$ 回以上適用することを考える：
- グリッドから $( h - 1 ) \times ( w - 1 )$ の矩形領域を選び，$\pi$ [rad] 回転させる*1．
$20$ 回以内の操作で，任意のセル $( i, j )$ に書かれている数が $( i - 1 ) \times w + j$ であるような状態（平易に言うと，$1$ 以上 $h w$ 以下の整数がグリッドに row-oriented で昇順に書かれている状態）にできるか判定し，できる場合は必要な操作回数の最小値を出力し，そうでないならばそれを報告せよ．
制約
- $3 \leq h, w \leq 8$
解法
「基本は全探索」といった格言がある[要出典]ように，まずは全探索から考えてみます．回転させる矩形領域の選び方は，領域の縦・横がそれぞれグリッドの縦・横よりちょうど $1$ ずつ小さいだけなので，左上寄り・右上寄り・左下寄り・右下寄りの $4$ 通りしかありません．各状態から $4$ 通りに分岐していくので，ちょうど $k$ 手で到達できる状態の数は高々 $4^k$ となります．$20$ 手以内で到達できる盤面の個数だと，各 $k$ ($0 \leq k \leq 20$) について和をとって，$\sum\limits_{ 0 \leq k \leq 20 } 4^k \simeq 1.5 \times 10^{ 12 }$ で抑えられることになりますが，これではまずいです．同じ矩形領域に対して連続して操作を行うと元に戻ってしまって意味が無いということを踏まえると，初手以外は選択肢が実質 $3$ つということになり状態数が減りますが，それでもまだ $4 \sum\limits_{ 0 \leq k \leq 19 } 3^k \simeq 7.0 \times 10^9$ で抑えられる感じなので，もう少し工夫する必要があります．
ところで，任意の操作について「同じ異矩形領域に対して操作する」という（同コストの）逆操作が存在しているので，ある状態 $A$ からある状態 $B$ への最小手数と，$B$ から $A$ への最小手数は同じになります．このことを使うと，競プロ界隈で「両側探索」と呼ばれたり呼ばれなかったりする手法を使うことができます（世間的には「双方向探索」っぽい）．すなわち，初期状態から $10$ 手までの範囲と，終状態から $10$ 手までの範囲をそれぞれ探索し，共通して到達できる状態の内で最小手数の和が最小なものを求めます．$10$ 手読むだけならば，状態数は $4 \sum\limits_{ 0 \leq k \leq 9 } 3^k \simeq 1.9 \times 10^5$ で抑えられ，各状態でよほど重い操作をしなければ間に合います．
では $10$ 手以内の探索はどうすればよいかというと，幅優先探索 (Breadth-First Search : BFS) を行えばよいです．ある状態 $s$ に初期状態から到達する最小手数を $d_s$ ，終状態から到達する最小手数を $\hat d_s$ とすると，$\min\limits_s( d_s + \hat d_s )$ を求めればよいです（到達できない状態＝探索で出現しなかった状態 $s$ についてはそれぞれ $d_s = \infty, \hat d_s = \infty$ と見做す）．有効な $s$ についてだけ値を計算していくには，$d_s \neq \infty$ なる $s$ を総当りし，更に $\hat d_s \neq \infty$ なら上記値を求めて暫定最小値を更新するようにすればよく，各状態に対する最小手数を std::map で保持することにすれば，片側を for-each で舐め，他方には std::map::find をしてあげればよいです．
コード
constexpr auto INF = LIM<>::max() / 2; bool completed( const VVI &A ) { const int H = SZ( A ), W = SZ( A[0] ); REP( i, H ) { REP( j, W ) { if ( A[i][j] != i * W + j ) { return false; } } } return true; } map< VVI, int > solve( const VVI &A ) { const int H = SZ( A ), W = SZ( A[0] ); map< VVI, int > distances; distances[A] = 0; queue< VVI > que; que.push( A ); while ( !que.empty() ) { const VVI A = que.front(); que.pop(); if ( 10 <= distances[A] ) { continue; } REP( x, 2 ) { REP( y, 2 ) { VVI B( A ); REP( i, H - 1 ) { REP( j, W - 1 ) { B[ i + x ][ j + y ] = A[ ( H - 1 ) - ( i + 1 ) + x ][ ( W - 1 ) - ( j + 1 ) + y ]; } } if ( !EXISTS( distances, B ) ) { distances[B] = distances[A] + 1; que.push( B ); } } } } return move( distances ); } int main() { IN( int, H, W ); VVI A( H, VI( W ) ); cin >> A; FOR( row, A ) { FOR( a, row ) { --a; } } VVI B( H, VI( W ) ); REP( i, H ) { iota( ALL( B[i] ), i * W ); } auto res1 = solve( A ); auto res2 = solve( B ); int res = INF; FOR( p, res1 ) { if ( EXISTS( res2, p.fst ) ) { chmin( res, res1[ p.fst ] + res2[ p.fst ] ); } } cout << ( res == INF ? -1 : res ) << endl; return 0; }
*1:詳細については原文参照のこと．
