Codeforces #910 : Div2 F. Vova Escapes the Matrix

割とコードが長くてめんどい。
https://codeforces.com/contest/1898/problem/F

問題

グリッドが与えられ、プレイヤーの初期位置が与えられる。
グリッドは一部進入不可となっている。
プレイヤーは隣接マスをたどり、グリッド外周部に到達しようとする。

この時、初期状態は以下のいずれかである。

• グリッド外周部に移動できない。
• グリッド外周部のうち、1マスだけに移動できる。
• グリッド外周部のうち、2マス以上に移動できる。

状態を変えない範囲で、進入不可マスを増やしたい。
最大何マス増やせるか。

解法

• グリッド外周部に移動できない。
  • この時は全マス進入不可マスで埋めてよい。
• グリッド外周部のうち、1マスだけに移動できる。
  • この時は、外周部の最短ルートだけ残し、後は進入不可マスで埋めてよい。
• グリッド外周部のうち、2マス以上だけに移動できる。
  • 2マス残すのが最短。そこで、各マスから各外周部までの最短距離のうち上位2位までと、初期位置までの距離を求めよう。その3つの和が最少のものを残し、後は進入不可マスで埋めてよい。

int T,H,W;
string S[1010];
int D[1010][1010];
int Da[1010][1010];
int Dx[1010][1010];
int Db[1010][1010];
int Dy[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		FOR(y,H) cin>>S[y];
		int ty,tx;
		int numb=0;
		int space=0;
		FOR(y,H) FOR(x,W) {
			if(S[y][x]=='V') {
				S[y][x]='.';
				ty=y;
				tx=x;
			}
			if(S[y][x]=='.') space++;
			D[y][x]=1<<25;
			Da[y][x]=1<<25;
			Dx[y][x]=1<<25;
			Db[y][x]=1<<25;
			Dy[y][x]=1<<25;
		}
		
		D[ty][tx]=0;
		queue<int> Q;
		Q.push(ty*1000+tx);
		int type=0,mi=1<<25;
		int d[]={0,1,0,-1};
		while(Q.size()) {
			y=Q.front()/1000;
			x=Q.front()%1000;
			Q.pop();
			if((y==0||y==H-1||x==0||x==W-1)) {
				type++;
				if(y!=ty||x!=tx) mi=min(mi,D[y][x]);
			}
			FOR(i,4) {
				int ty=y+d[i];
				int tx=x+d[i^1];
				if(ty<0||ty>=H||tx<0||tx>=W||S[ty][tx]=='#') continue;
				if(D[ty][tx]==1<<25) {
					D[ty][tx]=D[y][x]+1;
					Q.push(ty*1000+tx);
				}
			}
		}
		FOR(y,H) FOR(x,W) {
			if((y==0||y==H-1||x==0||x==W-1)&&S[y][x]=='.') {
				Da[y][x]=0;
				Dx[y][x]=y*W+x;
				Q.push(y*1000+x);
			}
		}
		while(Q.size()) {
			y=Q.front()/1000;
			x=Q.front()%1000;
			Q.pop();
			FOR(i,4) {
				int ty=y+d[i];
				int tx=x+d[i^1];
				if(ty<0||ty>=H||tx<0||tx>=W||S[ty][tx]=='#') continue;
				if(Da[ty][tx]>Da[y][x]+1&&Dy[ty][tx]!=Dx[y][x]) {
					Da[ty][tx]=Da[y][x]+1;
					Dx[ty][tx]=Dx[y][x];
					Q.push(ty*1000+tx);
				}
				if(Da[ty][tx]>Db[y][x]+1&&Dy[ty][tx]!=Dy[y][x]) {
					Da[ty][tx]=Db[y][x]+1;
					Dx[ty][tx]=Dy[y][x];
					Q.push(ty*1000+tx);
				}
				if(Db[ty][tx]>Da[y][x]+1&&Dx[ty][tx]!=Dx[y][x]) {
					Db[ty][tx]=Da[y][x]+1;
					Dy[ty][tx]=Dx[y][x];
					Q.push(ty*1000+tx);
				}
				if(Db[ty][tx]>Db[y][x]+1&&Dx[ty][tx]!=Dy[y][x]) {
					Db[ty][tx]=Db[y][x]+1;
					Dy[ty][tx]=Dy[y][x];
					Q.push(ty*1000+tx);
				}
			}
		}
		
		int ret=0;
		if(type==0) {
			ret=space-1;
		}
		else if(type==1) {
			if((ty==0||ty==H-1||tx==0||tx==W-1)) mi=0;
			ret=space-(mi+1);
		}
		else if(ty==0||ty==H-1||tx==0||tx==W-1){
			ret=space-(mi+1);
		}
		else {
			
			ret=-1<<20;
			FOR(y,H) FOR(x,W) if(D[y][x]<1<<20) {
				if(y==0||y==H-1){
					if(S[y][x-1]=='.'||S[y][x+1]=='.') {
						ret=max(ret,space-(D[y][x]+2));
					}
				}
				else if(x==0||x==W-1){
					if(S[y-1][x]=='.'||S[y+1][x]=='.') {
						ret=max(ret,space-(D[y][x]+2));
					}
				}
				else {
					ret=max(ret,space-(D[y][x]+1)-Da[y][x]-Db[y][x]);
				}
			}
		}
		
		cout<<ret<<endl;
	}
}

まとめ

難しくはないけど面倒な問題。
具体的な埋め方まで求める必要無くて良かったね。