Bayan 2015 Contest Elimination : C - Grid History

BayanのEliminationラウンドに参加。
前半は運営のグダグダもあり苦戦したけど、後半C,Eを解いてTシャツ圏内に入れた。
http://contest.bayan.ir/en/contest/elimination_2014/problem/C/

問題

N*Mのグリッドがあり、各セルの初期値は0である。
プレイヤーは任意のセルからスタートし、隣接マスをたどっていくという処理を行う。
その際、通過したマスには1,2,3...と段々数字をインクリメントさせながら格納していく。
(同じマスは複数回通っても良く、そのたび数字は上書きされる)

最終的なグリッドの状態が与えられるので、そのような移動は可能か答えよ。

解法

最終的なグリッドにおいて、数字の小さなマスの順に辿っていくことを考える。
この場合、以下の条件を満たすなら条件を満たす移動は可能である。
セルAの次に大きな数値のセルをBとしたとき：

• A→Bへの移動は、セルAの値以上のセルだけを通って到達できる。
• かつ、その際の最短移動距離はセルBとセルAの数値の差以下である。
• かつ、最短移動距離とセルBとセルAの数値の差の偶奇は一致する。偶奇が一致すれば最短移動距離がセルBとセルAの数値の差より短い場合、途中で２セルを往復することで数値の増分を嵩増しできる。
• ただし、最後の２セルだけは隣接してかつ数値の差が１である。なぜなら往復して数値を嵩増しする２セルがないためである。

A→Bの最短距離は適当なBFSでO(NM)なので、全体でO(N^2*M^2)で解ける。

int H,W;
ll A[51][51];
vector<pair<int,int> > V;
int ok[51][51];

int dist(int ty,int tx,int sy,int sx) {
	int y,x,i;
	int di[51][51];
	FOR(y,H) FOR(x,W) di[y][x]=100000;
	di[ty][tx]=0;
	queue<int> Q;
	Q.push(ty*100+tx);
	while(Q.size()) {
		int k=Q.front();
		Q.pop();
		int cy=k/100,cx=k%100;
		FOR(i,4) {
			int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
			int ttx=cx+dx[i],tty=cy+dy[i];
			if(ttx<0 || tty<0 || ttx>=W || tty>=H || ok[tty][ttx]==0) continue;
			if(di[tty][ttx]>di[cy][cx]+1) {
				di[tty][ttx]=di[cy][cx]+1;
				Q.push(tty*100+ttx);
			}
		}
	}
	return di[sy][sx];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	V.clear();
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) {
		cin>>A[y][x];
		ok[y][x]=1;
		V.push_back(make_pair(A[y][x],y*100+x));
	}
	sort(V.begin(),V.end());
	
	y=V[0].second/100;
	x=V[0].second%100;
	for(i=1;i<V.size();i++) {
		int ty=V[i].second/100;
		int tx=V[i].second%100;
		ok[y][x]=0;
		int d=dist(y,x,ty,tx);
		if(d>=10000) return _P("NO\n");
		
		if(V[i].first-V[i-1].first<d) return _P("NO\n");
		if((V[i].first-V[i-1].first)%2!=d%2) return _P("NO\n");
		if(i==V.size()-1) {
			if(d!=1 || V[i].first-V[i-1].first!=1) return _P("NO\n");
		}
		
		x=tx; y=ty;
	}
	_P("YES\n");
}

まとめ

これはアプローチはすぐ思いついたけど、7WAとかなりコーナーケースの分類に手こずった。