Codeforces #639 Div1 B. Monopole Magnets

また問題設定がややこしい。
https://codeforces.com/contest/1344/problem/B

問題

N極とS極片方だけを持つ仮想的なで電磁石を考える。

グリッド上に両磁石を配置したとする。このグリッドの各セルは白黒で塗られている。
両磁石が同じ列または同じ行にあるとき、両者に同時に電源を入れるとN極の磁石が1マスS極の磁石に向け動く。

ここで、以下を満たすようにN極・S極の磁石を配置したい。

• 各列・各行最低1個はS極の磁石がある。
• 上記手順でN極を動かしたとき、
  • 全黒マスはN極の磁石が移動し得る
  • 全白マスはN極の磁石が移動し得ない

条件を満たす配置を行うとき、N極の磁石は最低何個必要か。

解法

まず黒マスは全部S極の磁石を配置してしまってよい。
あとは以下を確認すればよい。

• 各列・各行に最低1個は黒マスがある。
• 黒マスの連結成分は凸である
• 各行・各列に2個以上の連結成分が現れない。

後ろ2つの条件は、隣接マスをUnion-Findでくっ付けた後、各行・各列で1つだけの連結成分が途中白マスを含まず連続しているかをチェックするとよい。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1000000> uf;

int H,W;
string S[3030];
int R[1010],C[1010],T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='#') R[y]++,C[x]++,T++;
	}
	
	if(T==0) return _P("0\n");
	FOR(y,H) if(R[y]==0) {
		FOR(x,W) if(C[x]==0) break;
		if(x==W) return _P("-1\n");
	}
	FOR(x,W) if(C[x]==0) {
		FOR(y,H) if(R[y]==0) break;
		if(y==H) return _P("-1\n");
	}
	
	
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='#') {
		if(y&&S[y-1][x]=='#') uf(y*1000+x,(y-1)*1000+x);
		if(x&&S[y][x-1]=='#') uf(y*1000+x,y*1000+x-1);
	}
	
	FOR(y,H) if(R[y]) {
		deque<int> D;
		FOR(x,W) {
			if(S[y][x]=='.') r=-1;
			else r=uf[y*1000+x];
			if(D.empty() || D.back()!=r) D.push_back(r);
		}
		while(D.size()&&D.front()==-1) D.pop_front();
		while(D.size()&&D.back()==-1) D.pop_back();
		if(D.size()>1) return _P("-1\n");
	}
	FOR(x,W) if(C[x]) {
		deque<int> D;
		FOR(y,H) {
			if(S[y][x]=='.') r=-1;
			else r=uf[y*1000+x];
			if(D.empty() || D.back()!=r) D.push_back(r);
		}
		while(D.size()&&D.front()==-1) D.pop_front();
		while(D.size()&&D.back()==-1) D.pop_back();
		if(D.size()>1) return _P("-1\n");
	}
	
	int num=0;
	FOR(y,H) FOR(x,W) if(S[y][x]=='#' && uf[y*1000+x]==y*1000+x) num++;
	cout<<num<<endl;
	
	
	
}

まとめ

解法ありきで無理やり問題設定作ってる感じで、問題文読むのがしんどい。