kmjp's blog

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

CODE FESTIVAL 2014 上海 : I - Obstruction

気づけば簡単なのだけど、本番気づかなかった。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_i

問題

N*Nのグリッドがある。各セルは白か黒の何れかである。

プレイヤーは最初(0,0)のセルにおり、隣接セルを辿って(N-1,N-1)に移動したい。
移動の度、敵は白マスの1か所をふさぎ、プレイヤーの移動を防止することができる。
敵がどのように白マスをふさいでも、プレイヤーが目的地に移動できるかどうか答えよ。

解法

目的地から逆向きに「目的地に到達可能なセル」の集合を求めていく。
「目的地に到達可能なセル」は、隣接マスに「目的地に到達可能な黒セル」があるか、目的地に到達可能な白セル」が2個以上ある場合である。

よって目的地からBFSし、隣接マスに「目的地に到達可能な黒セル」「目的地に到達可能な白セル」の数を加算していくことで、順次「目的地に到達可能なセル」を求めることができる。

int N;
string S[1001];
int num[1001][1001],vis[1001][1001];

void solve() {
	int i,j,k,l,r,x,y,x2,y2; string s;
	
	cin>>N;
	FOR(y,N) cin>>S[y];
	
	num[N-1][N-1]=2;
	vis[N-1][N-1]=1;
	queue<int> Q;
	Q.push((N-1)*1000+(N-1));
	
	while(Q.size()) {
		int k=Q.front();
		Q.pop();
		int cy=k/1000,cx=k%1000;
		FOR(i,4) {
			int dd[4]={0,1,0,-1};
			int ty=cy+dd[i],tx=cx+dd[i^1];
			if(tx<0||ty<0||tx>=N||ty>=N) continue;
			if(vis[ty][tx]) continue;
			num[ty][tx]++;
			if(S[cy][cx]=='#') num[ty][tx]+=2;
			
			if(num[ty][tx]>=2) vis[ty][tx]=1, Q.push(ty*1000+tx);
		}
	}
	
	if(vis[0][0]) _P("YES\n");
	else _P("NO\n");
}

まとめ

本番思いつかなかったなぁ。