D - パズル

[Q] https://atcoder.jp/contests/indeednow-quala/tasks/indeednow_2015_quala_4

スライドパズルの最適解を探索する問題。
AOJで全く同じ問題をみんなで解いたことがありました。
[Q] https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_C

バックトラックで全探索。4^26通り検証しつつ、3つの枝切りを考えます。
1. 前の手と同じ動作を省略

2. 今の盤面と正解盤面で距離を比較して、明らかに残り手数で完成しないなら打ち切る。

(3. 少ない手数から、だんだん大きくしていく。)
手数1で整うと仮定して4^1をみる。
ダメだったら手数2で整うと仮定して4^2を見る。
・・・
ダメだったら手数26で整うと仮定して4^26を見る。
いきなり4^26を見に行くより、軽いケースで探索が早くなる。

実装。146ms。
1msで終わっている人がたくさんいてすごい。

ll H, W, sy, sx;
ll C[6][6];

ll eval(){
 ll ret = 0;
 rep(i, H) rep(j, W){
   ll c = C[i][j];
   if (c==-1) c=H*W-1;
   ret += abs(c/W-i) + abs(c%W-j); // 正解盤面とのマンハッタン距離
 }

 return ret;
}

bool dfs(ll depth, ll fin, ll y, ll x, ll py, ll px){
 ll dif = eval();
 if (dif == 0) return true;
 if ((fin-depth)*2 < dif) return false; // 1手スライドさせたら、距離が2縮まる。
 rep(k, 4){
   ll ny = y+dy[k];
   ll nx = x+dx[k];
   if (ny<0 || ny>=H || nx<0 || nx>=W) continue;
   if (ny==py && nx==px) continue; // 前の手は見ない
   swap(C[y][x], C[ny][nx]); // バックトラック
   if (dfs(depth+1, fin, ny, nx, y, x)) return true; // 1回答えが見つかったら終了
   swap(C[y][x], C[ny][nx]); // 復元
 }
 return false;
}

int main(){
 cincout();
 
 cin >> H >> W;
 rep(i, H) rep(j, W){
   cin >> C[i][j];
   --C[i][j];
   if (C[i][j] == -1){
     sy=i;
     sx=j;
   }
 }

 for(ll i=0; i<=24; ++i){ // あがり手数を仮定
   if (dfs(0, i, sy, sx, -1, -1)){ // 1回答えが見つかったら終了
     cout << i << endl;
     return 0;
   }
 }
 cout << -1 << endl;
}

https://atcoder.jp/contests/indeednow-quala/submissions/26022674