TopCoder SRM 544 Div1 Medium FlipGame

この回は妙に簡単だと思ったけど、案の定正答者が多かった。
http://community.topcoder.com/stat?c=problem_statement&pm=11974

問題

01が敷き詰められた２次元グリッドが与えられる。
ここで、左上から右下に向け隣接マスをたどって１回移動すると、たどったマスおよびその下側にあるマスは全て01が反転する。
全ての数字を0にするには、最小何回左上から右下に移動すればよいか。

解法

残された1をすべて囲いきる最少のパスをたどる、という処理を1が無くなるまでGreedyに繰り返せばよい。
例えばこんな感じ。

1100000    **00000    0000000
0010100    0****00    1101000
1101010 → 1101**0 → 0010100
0000001    00000**    1111110

class FlipGame {
	public:
	int minOperations(vector <string> board) {
		int H=board.size(),W=board[0].size();
		int ret=0;
		int x,y,h;
		
		while(1) {
			int num=0;
			FOR(y,H) num+=count(board[y].begin(),board[y].end(),'1');
			if(num==0) break;
			ret++;
			h=H;
			for(x=W-1;x>=0;x--) {
				FOR(y,H) if(board[y][x]=='1') h=min(h,y);
				for(y=h;y<H;y++) board[y][x]^=1;
			}
		}
		return ret;
	}
}

まとめ

Mediumの割に難易度もコード量も控えめだね。