AtCoder AGC #014 : C - Closed Rooms

また解くの遅い…。
http://agc014.contest.atcoder.jp/tasks/agc014_c

問題

H*Wのグリッドが与えられる。
一部のマスは埋められている。
プレイヤーの初期位置が与えられており、最も外側のマス群のいずれかに移動したい。

その際、整数Kに対し1ターンで次の順で処理を行える。

• 隣接マスをたどり最大K回移動する
• 任意の埋まったマスを最大K個空にする

必要な最小ターン数を求めよ。

解法

最初のターンは埋まったマスはどうしようもないので、まずは空マスだけでK回以内で移動可能な範囲をBFSで探索しよう。
以降、次のターンの前半で移動する分を、今のターンの後半で空にする、と考えると、以降のターンは任意に移動できる。
そのため２ターン目以降は埋まったマスを無視して、最短で端のマスに到達するケースを考えればよい。

int H,W,K;
string S[808];
int SY,SX;

int dist[808][808];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			if(S[y][x]=='S') {
				S[y][x]='.';
				SY=y;
				SX=x;
			}
			dist[y][x]=1<<20;
		}
	}
	
	dist[SY][SX]=0;
	queue<int> Q;
	Q.push(SY*1000+SX);
	int mi=1<<20;
	
	while(Q.size()) {
		int cy=Q.front()/1000;
		int cx=Q.front()%1000;
		Q.pop();
		
		mi=min(mi,1+(cy+K-1)/K);
		mi=min(mi,1+(cx+K-1)/K);
		mi=min(mi,1+((H-1-cy)+K-1)/K);
		mi=min(mi,1+((W-1-cx)+K-1)/K);
		if(dist[cy][cx]==K) continue;
		
		FOR(i,4) {
			int dd[]={1,0,-1,0};
			int ty=cy+dd[i];
			int tx=cx+dd[i^1];
			if(ty<0 || tx<0 || ty>=H || tx>=W) continue;
			if(S[ty][tx]=='#') continue;
			if(dist[ty][tx]>dist[cy][cx]+1) {
				dist[ty][tx]=dist[cy][cx]+1;
				Q.push(ty*1000+tx);
			}
		}
	}
	cout<<mi<<endl;
}

まとめ

本番無駄に2回BFSやってしまった。