Codeforces #192 Div1. A. Purification

CF#192はA,Bを解けてそこそこの順位だった。
http://codeforces.com/contest/329/problem/A

問題

NxNのグリッドが与えられる。
すべてのマスはEvilであり、これらのマスを浄化したい。
あるマスを浄化魔法を唱えると、そのマスと上下左右のマスが浄化される。

ここで、いくつかのマスは浄化魔法が唱えられない。
すべてのマスを浄化するのに必要な浄化魔法を唱えるマスを答えよ。

解法

各行で1回ずつ、または各列で1回ずつ浄化魔法を唱えられれば全マスを浄化できる。

int N;
string S[101];
int ok[101];
void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	
	MINUS(ok);
	FOR(y,N) {
		FOR(x,N) if(S[y][x]=='.') ok[y]=x;
		if(ok[y]==-1) goto ngng;
	}
	FOR(y,N) _P("%d %d\n",y+1,ok[y]+1);
	return;
	
	ngng:
	MINUS(ok);
	FOR(x,N) {
		FOR(y,N) if(S[y][x]=='.') ok[x]=y;
		if(ok[x]==-1) {
			_P("-1\n");
			return;
		}
	}
	FOR(x,N) _P("%d %d\n",ok[x]+1,x+1);
}

まとめ

今回のAは割と簡単。