TopCoderOpen 2018 Round3B Easy SquareCutout

出てたら0点だったな…
http://community.topcoder.com/stat?c=problem_statement&pm=14966

問題

無限の広さのグリッドで、一部N*Nの正方形領域だけ黒く塗られており、残りは白く塗られているとする。
今グリッドの一部H*Wの領域を切り抜いた状態が与えられる。

このグリッドは前述の条件で作った形状であり得るか判定せよ。
あり得るなら、あり得るNの最小値を求めよ。

解法

黒マスが1つもないなら、切り抜いた領域の外側に正方形領域があるので1を答えよう。

それ以外の場合、まず黒マスが（正方形の一部をくりぬいたとして）長方形領域を成すか判定する。
そうでないなら、前述の条件で作った形状ではない。

黒マスが長方形を成す場合、黒マスが左右の端または上下の端に達する場合、幅・高さがいくらでも大きくできることになる。
ここから、グリッド内の長方形を含む最小の正方形長を求めよう。

class SquareCutout {
	public:
	int verify(vector <string> C) {
		int H=C.size();
		int W=C[0].size();
		int L=100,R=-1,U=100,D=-1;
		int x,y;
		FOR(y,H) FOR(x,W) if(C[y][x]=='#') {
			L=min(L,x);
			R=max(R,x);
			U=min(U,y);
			D=max(D,y);
		}
		if(L==100) return 1;
		for(y=U;y<=D;y++) for(x=L;x<=R;x++) if(C[y][x]=='.') return 0;
		int w=R-L+1;
		int h=D-U+1;
		if((L==0)||(R==W-1)) w=max(w,h);
		if((U==0)||(D==H-1)) h=max(w,h);
		if((L==0)||(R==W-1)) w=max(w,h);
		if((U==0)||(D==H-1)) h=max(w,h);
		if(w!=h) return 0;
		return w;
	}
}

まとめ

シンプルながら意外にコーナーケースの多い問題。