AtCoder ARC #112 : D - Skate

Eまでサクサク解けたので出来の良かった回。
https://atcoder.jp/contests/arc112/tasks/arc112_d

問題

H*Wのグリッドが与えられる。
グリッドの周辺は壁である。
各セルは、氷か地面のいずれかである。
今あるセルにいて四方のいずれかの隣接セルに移動しようとすると、そのセルが氷である場合、そのまま次のセルに進んでしまう。

今任意のセルから初めて、任意のセルを通過できるようにするため、いくつ氷のセルを地面のセルにする必要があるか求めよ。

解法

四隅は常に到達・停止可能なので、そのセルは地面であると考えてよい。
そのため、左上隅のマスから、全セル通過可能な条件を考えよう。
その条件は、

• 左上隅から(行を問わず)全列に停止可能
• 左上隅から(列を問わず)全行に停止可能

のいずれかを満たすことである。
いずれも満たさない場合、停止不可能な行のうち停止不可能な列には、どうやっても通過できない。

あとは上記箇条書きの判定である。
行と列に対応する(H+W)頂点の二部グラフを作り、地面のあるセルに対応する行と列の間に辺を張ろう。
この二部グラフで全行または全列が連結となるよう辺を増やしていけばよい。

int H,W;
string S[1010];

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<2020> uf,uf2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	FOR(y,H) cin>>S[y];
	S[0][0]=S[H-1][0]=S[0][W-1]=S[H-1][W-1]='#';
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='#') uf(y,1000+x),uf2(y,1000+x);
	int a=0,b=0;
	FOR(y,H) if(uf[0]!=uf[y]) a++, uf(0,y);
	FOR(x,W) if(uf2[0]!=uf2[1000+x]) b++, uf2(0,1000+x);
	cout<<min(a,b)<<endl;
}

まとめ

考察が終わると、コードは簡単。