Indeedなう（予選A） : D - パズル

ABCよりはちょっと難しいけど、ARCのDよりは簡単かも。
http://indeednow-quala.contest.atcoder.jp/tasks/indeednow_2015_quala_4

問題

盤面のサイズが4*4固定ではなく、H*Wである15パズルの盤面が与えられる。
これらを初期状態に戻すのに必要な最小手数を求めよ。
なお、最大でも24手で戻せることが保証されている。

解法

半分全列挙(両側探索の方が正確か？)を用いる。
すなわち与えられた状態から12手まで探索し、また最終形から逆向きに12手まで探索して、両者からともに到達可能な状態があれば、その手数の和の最小値を求める。

1手あたり空マスの移動が4通りあるが、実際は直前と逆向きの探索など以前と同じ状態に戻る探索は省略できるので2*(3^12)より小さい探索空間となる。

int H,W;
typedef vector<vector<int> > TT;
TT v;
map<TT,int> P[2];

void dfs(TT& c,int zy,int zx,int num,int id) {
	int i;
	if(num>12) return;
	if(P[id].count(c) && P[id][c]<num) return;
	P[id][c]=num;
	
	FOR(i,4) {
		int dd[4]={1,0,-1,0};
		int ty=zy+dd[i],tx=zx+dd[i^1];
		if(tx<0 || ty<0 || tx>=W || ty>=H) continue;
		swap(c[zy][zx],c[ty][tx]);
		dfs(c,ty,tx,num+1,id);
		swap(c[zy][zx],c[ty][tx]);
	}
}


void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>H>>W;
	TT s,t;
	FOR(y,H) s.push_back(vector<int>(W));
	FOR(y,H) t.push_back(vector<int>(W));
	int sy,sx;
	
	FOR(y,H) FOR(x,W) {
		cin>>s[y][x];
		if(s[y][x]==0) sx=x,sy=y;
		t[y][x]=((y)*W + (x+1))%(H*W);
	}
	dfs(s,sy,sx,0,0);
	dfs(t,H-1,W-1,0,1);
	int mi=24;
	ITR(it,P[0]) if(P[1].count(it->first)) mi=min(mi,it->second+P[1][it->first]);
	cout<<mi<<endl;
}

まとめ

最初盤面の状態を配列で持ったらless演算が未定義のためmapが使えなかった。
おかげでvectorのvectorに書き直しが発生して大幅タイムロス。
vectorはlessが定義されていて便利だね。