Codeforces #300 Div1 D. Weird Chess

yukicoderで似た問題を見た。
http://codeforces.com/contest/538/problem/D

問題

N*Nのチェスの盤面が与えられる。
盤面には1種類の駒がいくつかある。

• 'o'は今駒がいるマスである。
• 'x'はいずれかの駒が1手でたどり着けるマスである。
• '.'はその他のマスである。

駒が1手で移動可能な領域のうち、

• 'x'のマスはいずれかの駒が1手で辿りつける
• '.''o'のマスはどの駒も1手でたどり着けない

ような物の1例を答えよ。

解法

yukicoderで近い問題を見たね。
No.179 塗り分け - yukicoder

愚直な総当たりで良い。
各'x'マスについて、どの駒が移動可能か総当たりする。
'x'に到達できる'o'マスを決めたら、他の'o'駒が同じ分移動したとき、'x'以外のマスに到達しないか判定する。
どれも'x'以外のマスに到達しないなら、その移動は可能であると判断できる。

int N;
string S[51];
string R[101];
vector<pair<int,int> > C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S[y];
		FOR(x,N) if(S[y][x]=='o') C.emplace_back(x,y);
	}
	if(C.empty()) return _P("NO\n");
	
	FOR(y,2*N-1) s+=".";
	FOR(y,2*N-1) R[y]=s;
	R[N-1][N-1]='o';
	
	FOR(y,N) FOR(x,N) if(S[y][x]=='x') {
		int ok2=0;
		FORR(r,C) {
			int dx=x-r.first;
			int dy=y-r.second;
			int ok=1;
			FORR(r2,C) {
				int tx=r2.first+dx;
				int ty=r2.second+dy;
				if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
				if(S[ty][tx]=='.') {
					ok=0;
					break;
				}
			}
			if(ok==1) {
				ok2=1;
				R[N+dy-1][N+dx-1]='x';
				break;
			}
		}
		if(ok2==0) return _P("NO\n"); 
		
	}
	
	cout<<"YES"<<endl;
	FOR(y,2*N-1) cout<<R[y]<<endl;
}

まとめ

実装は若干手間取るものの、妙に簡単だと思ったら、D問題とはいえ1500ptでDiv2C/Div1A相当だった。