読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Codeforces #192 Div1. A. Purification

Codeforces

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は割と簡単。

広告を非表示にする