Codeforces #442 Div2 D. Olya and Energy Drinks

詰めが甘すぎて落とした。
http://codeforces.com/contest/877/problem/D

問題

H*Wの2次元グリッドが与えられる。
一部のマスは移動不可である。

1回の移動で、現在のマスから上下左右Kマス以内のマスに移動できるとする。
スタートとゴールのマスが与えられたとき、その間移動する最小移動回数を求めよ。

解法

ダイクストラの要領で各マスへの最小移動回数を求めていこう。
ただ普通にやるとTLEするので少し工夫する。

あるマスから1回で到達可能なマスを順次探索するとき、上下左右それぞれ1マス,2マス,3マス...と近い順に最小移動回数を更新していく。
その際、途中ですでに今いるマスと同じかそれ以下の移動回数で到達可能なマスに来たらそれ以上の探索は止める。
なぜなら、それ以降は最初からその(今いるマスと同じかそれ以下の移動回数で到達可能な)マスから探索すれば十分だからである。

こうして同じマスを何度も探索することを抑止すると普通にO(HW)で解けKに依存しない。

int H,W,K;
string S[1010];
int SY,SX,GY,GX;
int D[1010][1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) cin>>S[y];
	cin>>SY>>SX>>GY>>GX;
	SY--,SX--,GY--,GX--;
	
	FOR(y,H) FOR(x,W) D[y][x]=1<<20;
	int step=0;
	D[SY][SX]=0;
	queue<int> Q;
	Q.push(SY*1000+SX);
	
	while(Q.size()) {
		queue<int> NQ;
		
		while(Q.size()) {
			int cy=Q.front()/1000;
			int cx=Q.front()%1000;
			Q.pop();
			
			// up;
			for(i=1;i<=K;i++) {
				int ty=cy-i;
				int tx=cx;
				if(ty<0 || S[ty][tx]=='#' || D[ty][tx]<=D[cy][cx]) break;
				if(D[ty][tx]>step+1) D[ty][tx]=step+1, NQ.push(ty*1000+tx);
			}
			// down
			for(i=1;i<=K;i++) {
				int ty=cy+i;
				int tx=cx;
				if(ty>=H || S[ty][tx]=='#' || D[ty][tx]<=D[cy][cx]) break;
				if(D[ty][tx]>step+1) D[ty][tx]=step+1, NQ.push(ty*1000+tx);
			}
			// left;
			for(i=1;i<=K;i++) {
				int ty=cy;
				int tx=cx-i;
				if(tx<0 || S[ty][tx]=='#' || D[ty][tx]<=D[cy][cx]) break;
				if(D[ty][tx]>step+1) D[ty][tx]=step+1, NQ.push(ty*1000+tx);
			}
			// right
			for(i=1;i<=K;i++) {
				int ty=cy;
				int tx=cx+i;
				if(tx>=W || S[ty][tx]=='#' || D[ty][tx]<=D[cy][cx]) break;
				if(D[ty][tx]>step+1) D[ty][tx]=step+1, NQ.push(ty*1000+tx);
			}
		}
		
		swap(Q,NQ);
		step++;
	}
	
	if(D[GY][GX]>=1<<20) cout<<-1<<endl;
	else cout<<D[GY][GX]<<endl;
}

まとめ

誤ってO(HWK)な解法のままロックしてしまいTLEした。