AtCoder ARC #040 : C - Z塗り

今回はスプラトゥーン押し？
http://arc040.contest.atcoder.jp/tasks/arc040_c

問題

N*Nのグリッドがあり、一部が塗られている。
(r,c)を選択して１回塗るとき、(r,c') (c'≦c)及び(r+1,c'') (c≦c'')に相当するセルを全部塗ることができる。
全マスを塗るまでに最小何回塗る作業が必要か。

解法

上の行から貪欲に塗っている。
各行に塗っていないマスがある場合、その行の右端のマスを選択すればよい。

int N;
string S[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) cin>>S[y];
	
	int ret=0;
	FOR(y,N) {
		for(x=N-1;x>=0;x--) if(S[y][x]=='.') break;
		if(x<0) continue;
		ret++;
		FOR(i,x+1) S[y][i]='o';
		if(y<N-1) for(i=x;i<N;i++) S[y+1][i]='o';
	}
	
	cout<<ret<<endl;
}

まとめ

今回のCはARCにしても簡単だね。ABC並か。