Mujin Programming Challenge 2017 : B - Row to Column

なぜこれが本番中に解けないのか。
http://mujin-pc-2017.contest.atcoder.jp/tasks/mujin_pc_2017_b

問題

N*Nのグリッドがあり、各マスは白黒で埋められている。
任意の1行分のマスの状態をコピーし、任意の列に貼り付け上書きする、という処理を繰り返す。
全マスをコピーするには最小何回処理を行えばよいか。

解法

元々黒マスが0個の場合は、達成不可。
それ以外の場合、まず1行全部黒マスの行を作れれば、それを全(白マスが残っている)列に上書きすることで達成できる。

いまr行目をすべて黒くすることを考える。
いずれかの行でr列目が黒い列を探せれば、それをr行目が白マスである列に上書きしていくことができる。
r行目に黒い列がどこにもない場合、どこか別の黒いマスを見つけていったんr列目に貼り付けることで、↑の処理を実行できる。

int N;
vector<string> S;
int ret;
int R[501],C[501];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(y,N) {
		cin>>s;
		S.push_back(s);
		FOR(x,N) if(S[y][x]=='#') R[y]++, C[x]++;
	}
	
	if(count(R,R+N,0)==N) return _P("-1\n");
	
	int mi=101010;
	FOR(y,N) {
		int num=0;
		int add=0;
		FOR(x,N) if(S[y][x]=='.') num++;
		FOR(i,N) if(S[i][y]=='#') add=1;
		if(num && add==0) num++;
		FOR(x,N) if(C[x]!=N) num++;
		mi=min(mi,num);
	}
	
	cout<<mi<<endl;
}

まとめ

AtCoderのレートが徐々に落ちていってる…。