yukicoder : No.2838 Diagonals

ちょっと迷ったけど、気付けばかなりすんなり。
https://yukicoder.me/problems/no/2838

問題

H*Wのグリッドがあり、各セルにはマスがある場所とない場所がある。
各マスは、正方形か、それを対角線で区切った図形の計4種類の図形のいずれかを取る。
それぞれの図形の境界には境界線がある。
この図形を白黒で塗り分けたい。その際、境界線で区切られた両側は白黒異なる色となるようにしたい。

各マスの図形の取り方に対し、条件を満たす塗り分けができるのは何通りか。

解法

先に色の塗り分けを考える。それを(全体を白黒反転させた場合も、同じ図形と見なせるので)連結成分毎に2で割れば解となる。

あるマスを、対角線で区切った4つの三角形領域を考える。
もし左マスと上マスの色が確定している場合、上三角形と左三角形の色も確定する。
その場合、下三角形と右三角形は、上三角形と左三角形の色の組み合わせが何であれ、合わせて2通り取りえる。

左マスや上マスがない場合は、上三角形や左三角形の色も任意に選べるので、そこも2通り選べることになる。

int H,W;
string S[505];
const ll mo=998244353;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1<<20> uf; 

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	ll ret=1;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='#') {
			ret=ret*2%mo;
			if(y==0||S[y-1][x]=='.') ret=ret*2%mo;
			if(x==0||S[y][x-1]=='.') ret=ret*2%mo;
			if(y&&S[y-1][x]=='#') uf(y*500+x,(y-1)*500+x);
			if(x&&S[y][x-1]=='#') uf(y*500+x,(y-0)*500+x-1);
		}
	}
	FOR(y,H) FOR(x,W) if(S[y][x]=='#' && uf[y*500+x]==y*500+x) ret=ret*(mo+1)/2%mo;
	cout<<ret<<endl;
	
}

まとめ

ここまでは割と素直。