kmjp's blog

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

2012 WUPC2 : F - 僕は宇宙人

さて続いてF。こちらは本番ミスもあったけど、割とスムーズに解けた問題。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_06


メッセージボードを移動しつつ、メッセージを生成する。
各マスでは、上下左右どの方向から移動してきたかそれぞれ最小コストを覚えてき、1文字ずつDPで解いていけばよい。
前と同じ移動方向を取らないように注意。


開始はどこからでもよく、最初の移動で1文字目に行く必要があるので、1文字目だけは特別処理が必要。
1文字目は常に隣接マスから開始すればよいのでコストは1になる。

int H,W,L;
char msg[101];
char str[101][101];
int cost[2][101][101][4];
int la=99999999;
void solve() {
	int x,y,i,j,rr,TM,nc;
	int tx,ty;
	ll p;
	
	GET3(&H,&W,&L);
	ZERO(str);
	GETs(msg);
	FOR(y,H) GETs(str[y]);
	
	if(L<=1) {
		if(H==1 && W==1) {
			_P("-1\n");
		}
		else {
			FOR(y,H) FOR(x,W) {
				if(str[y][x]==msg[0]) {
					_P("1\n");
					return;
				}
			}
		}
		_P("-1\n");
		return;
	}
	
	ZERO(cost);
	FOR(y,H) FOR(x,W) {
		if(str[y][x]==msg[0]) {
			cost[0][y][x][0]=1;
			cost[0][y][x][1]=1;
			cost[0][y][x][2]=1;
			cost[0][y][x][3]=1;
			if(x==0) cost[0][y][x][0]=la;
			if(x==W-1) cost[0][y][x][1]=la;
			if(y==H-1) cost[0][y][x][2]=la;
			if(y==0) cost[0][y][x][3]=la;
		}
		else {
			cost[0][y][x][0]=la;
			cost[0][y][x][1]=la;
			cost[0][y][x][2]=la;
			cost[0][y][x][3]=la;
		}
	}
	
	for(nc=0;nc<L-1;nc++) {
		FOR(y,H) FOR(x,W) {
			FOR(i,4) cost[1-nc%2][y][x][i]=la;
		}
		
		FOR(y,H) FOR(x,W) {
			if(str[y][x]!=msg[nc]) continue;
			//0-→
			for(tx=x+1;tx<W;tx++) {
				if(str[y][tx]!=msg[nc+1]) continue;
				cost[1-nc%2][y][tx][0] = min(cost[1-nc%2][y][tx][0], cost[nc%2][y][x][1]+tx-x);
				cost[1-nc%2][y][tx][0] = min(cost[1-nc%2][y][tx][0], cost[nc%2][y][x][2]+tx-x);
				cost[1-nc%2][y][tx][0] = min(cost[1-nc%2][y][tx][0], cost[nc%2][y][x][3]+tx-x);
				break;
			}
			//1-←
			for(tx=x-1;tx>=0;tx--) {
				if(str[y][tx]!=msg[nc+1]) continue;
				cost[1-nc%2][y][tx][1] = min(cost[1-nc%2][y][tx][1], cost[nc%2][y][x][0]+x-tx);
				cost[1-nc%2][y][tx][1] = min(cost[1-nc%2][y][tx][1], cost[nc%2][y][x][2]+x-tx);
				cost[1-nc%2][y][tx][1] = min(cost[1-nc%2][y][tx][1], cost[nc%2][y][x][3]+x-tx);
				break;
			}
			//2-↑
			for(ty=y-1;ty>=0;ty--) {
				if(str[ty][x]!=msg[nc+1]) continue;
				cost[1-nc%2][ty][x][2] = min(cost[1-nc%2][ty][x][2], cost[nc%2][y][x][0]+y-ty);
				cost[1-nc%2][ty][x][2] = min(cost[1-nc%2][ty][x][2], cost[nc%2][y][x][1]+y-ty);
				cost[1-nc%2][ty][x][2] = min(cost[1-nc%2][ty][x][2], cost[nc%2][y][x][3]+y-ty);
				break;
			}
			//3-下
			for(ty=y+1;ty<H;ty++) {
				if(str[ty][x]!=msg[nc+1]) continue;
				cost[1-nc%2][ty][x][3] = min(cost[1-nc%2][ty][x][3], cost[nc%2][y][x][0]+ty-y);
				cost[1-nc%2][ty][x][3] = min(cost[1-nc%2][ty][x][3], cost[nc%2][y][x][1]+ty-y);
				cost[1-nc%2][ty][x][3] = min(cost[1-nc%2][ty][x][3], cost[nc%2][y][x][2]+ty-y);
				break;
			}
		}
		
	}
	
	int res=la;
	FOR(y,H) FOR(x,W) FOR(i,4) res = min(res, cost[(L-1)%2][y][x][i]);
	
	if(res>=la) res=-1;
	_P("%d\n",res);
	return;
}

まとめ

4方向の処理を4回書いてしまったので見づらくなってしまった。
もうちょい綺麗に書けないもんかな。

最初、『進行中に伝えたい文字が見つかったら,直ちに止まる』の条件を読み飛ばして、途中の文字を通過できると思い込んでミスしてしまったのが残念。