kmjp's blog

競技プログラミング参加記です

Codeforces #270 Div1 E. Design Tutorial : Learn from a Game

Codeforces

難しくはないけど、面倒かつ色々解法のありそうな問題。
http://codeforces.com/contest/472/problem/E

問題

初期状態でN*Mのグリッド上にそれぞれ宝石が乗っている。
また、終了状態として同様にN*Mのグリッド上にそれぞれ宝石が乗っている。
パズドラと同様のルール（詳細は問題文参照）で１ターン宝石を動かした場合、初期状態から終了状態に遷移可能か答えよ。
可能なら移動手順を答えよ。

解法

NまたはMが1の時は、移動する宝石の始点と終点を総当たりして、遷移可能かチェックする。

よって以後はN,Mがともに２以上であることを前提とする。
まず最初に、同じ種類の宝石が複数あると処理が面倒なので、適当に１対１で対応付ける。
この時、各種類の宝石が初期状態と終了状態で異なる数だと遷移不能で終了。

それ以外は必ず解があるので、１つずつ宝石を移動していく。
最初に選択する宝石は、終了状態で一番左上に来るものを使う。
N*Mのグリッドのうち、まず上２行を残して下から１行目を右から左、２行目を右から左…と終了状態の場所に移動する。
例えば今(a,b)にある宝石を(x,y)に移動させたい場合、例えばa＜x,b＜yなら最初に選択する宝石を(a+1,b+1)までなんとかして動かし、(a,b)の宝石と交換すれば、(a,b)の宝石を(x,y)に近づけることができ、最終的に(x,y)に移動できる。

この際、最初に選択する宝石を(a+1,b+1)に動かす必要があるが、これは終了状態の位置に確定済みの宝石と、動かしたい(a,b)を除いたセルで適当にDFSして動かせばよい。
上２行は自由に移動可能なので、(a+1,b+1)に移動できないということはない。
a＜x,b＜yじゃない場合も、とにかく１マスずつ(x,y)に近づければよい。

ここまでやると、終了状態に確定していないのは上２行となる。
次は同様に右の列から順に左端１列が残るまで終了状態の位置に宝石を動かしていく。
最後残りは左上２マスなので、左上に来るべき最初に選択する宝石を左上に動かして終了。

int H,W;
int A[30][30],B[30][30];
int X[30][30],Y[30][30],F[30][30];
vector<int> R;

void single(bool rotate) {
	int i,j;
	int C[30];
	
	if(rotate) {
		FOR(i,H) swap(A[0][i],A[i][0]);
		FOR(i,H) swap(B[0][i],B[i][0]);
		swap(H,W);
	}
	
	memmove(C,A[0],sizeof(C));
	if(memcmp(C,B[0],sizeof(C))==0) {
		return _P("1 1\n");
	}
	FOR(i,W) {
		memmove(C,A[0],sizeof(C));
		for(j=i+1;j<W;j++) {
			swap(C[j],C[j-1]);
			if(memcmp(C,B[0],sizeof(C))==0) {
				_P("%d\n",j-i);
				_P("%d %d\n",rotate?i+1:1,rotate?1:(i+1));
				for(;i<j;i++) _P("%d %d\n",rotate?i+2:1,rotate?1:(i+2));
				return;
			}
		}
		memmove(C,A[0],sizeof(C));
		for(j=i-1;j>=0;j--) {
			swap(C[j],C[j+1]);
			if(memcmp(C,B[0],sizeof(C))==0) {
				_P("%d\n",i-j);
				_P("%d %d\n",rotate?i+1:1,rotate?1:(i+1));
				for(;i>j;i--) _P("%d %d\n",rotate?i:1,rotate?1:i);
				return;
			}
		}
	}
	_P("-1\n");
	
}

void moveone(int tarx,int tary,int sx,int sy) {
	int D[30][30],from[30][30];
	int x,y,dx,dy,i;
	FOR(x,30) FOR(y,30) D[x][y]=1000;
	D[sy][sx]=0;
	queue<int> Q;
	Q.push(sy*100+sx);
	while(Q.size()) {
		int cy=Q.front()/100, cx=Q.front()%100;
		if(cy==tary && cx==tarx) break;
		Q.pop();
		for(dx=-1;dx<=1;dx++) for(dy=-1;dy<=1;dy++) {
			int tx=cx+dx,ty=cy+dy;
			if(tx<0 || tx>=W || ty<0 || ty>=H || F[ty][tx] || D[ty][tx]<=D[cy][cx]+1) continue;
			from[ty][tx]=cy*100+cx;
			D[ty][tx]=D[cy][cx]+1;
			Q.push(ty*100+tx);
			if(ty==tary && tx==tarx) break;
		}
	}
	
	vector<int> V;
	while(tarx!=sx || tary!=sy) {
		V.push_back(tary*100+tarx);
		y=tary,x=tarx;
		tary=from[y][x]/100;
		tarx=from[y][x]%100;
	}
	FOR(i,V.size()) {
		tary=V[V.size()-1-i]/100;
		tarx=V[V.size()-1-i]%100;
		int j=A[tary][tarx];
		
		A[sy][sx]=j;
		A[tary][tarx]=0;
		
		X[j/W][j%W]=sx;
		Y[j/W][j%W]=sy;
		X[0][0]=sx=tarx;
		Y[0][0]=sy=tary;
		R.push_back(tary*100+tarx);
	}
}

void move(int tx,int ty) {
	F[Y[ty][tx]][X[ty][tx]]=1;
	int x,y;
	
	while(A[ty][tx] != ty*W+tx) {
		int cx=X[ty][tx],cy=Y[ty][tx];
		int nx,ny;
		
		ny=cy+(ty>cy)-(ty<cy);
		nx=cx+(tx>cx)-(tx<cx);
		if(F[ny][nx] && ny>cy && nx<cx) ny=cy;
		moveone(nx,ny,X[0][0],Y[0][0]);
		swap(A[cy][cx],A[ny][nx]);
		X[ty][tx]=nx;
		Y[ty][tx]=ny;
		X[0][0]=cx;
		Y[0][0]=cy;
		F[cy][cx]=0;
		F[ny][nx]=1;
		
		R.push_back(cy*100+cx);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	FOR(y,H) FOR(x,W) cin>>B[y][x];
	
	if(H==1 || W==1) return single(W==1);
	FOR(y,H) FOR(x,W) A[y][x]+=1000;
	MINUS(X);
	FOR(y,H) FOR(x,W) {
		FOR(i,H) FOR(j,W) if(B[y][x]+1000==A[i][j]) {
			A[i][j]=y*W+x;
			X[y][x]=j;
			Y[y][x]=i;
			B[y][x]=1000;
		}
		if(X[y][x]<0) return _P("-1\n");
	}
	R.push_back(Y[0][0]*100+X[0][0]);
	for(y=H-1;y>1;y--) for(x=W-1;x>=0;x--) move(x,y);
	for(x=W-1;x>0;x--) for(y=1;y>=0;y--) move(x,y);
	if(A[0][0]!=0) R.push_back(0);
	
	_P("%d\n",R.size()-1);
	ITR(it,R) _P("%d %d\n",*it/100+1,*it%100+1);
}

まとめ

めんどうな問題ではあるが「宝石を目的位置に１マスずつ動かしていく場合、１マス先に最初に選択した宝石を動かしてswapする」ということを愚直に何度も行えばよいだけ。