CSAcademy Round #14 : C. Surrounded Rectangle

最後の問題で時間切れ。
https://csacademy.com/contest/round-14/#task/surrounded-rectangle

問題

H*Wのグリッドがあり、各セルは0,1の値が埋められている。
1で埋められた矩形領域で、かつ周囲が0で囲まれているものの最大面積を求めよ。

解法

1のセルを見つけたら、周囲8マスを再帰的にたどり、(斜めマスも含め)隣接セルの連結成分を求めよう。
以下を満たせば条件を満たす矩形領域となる。

• 周辺部を含まない
• 連結成分の幅×高さと、1のセルの数が一致すれば矩形領域は1で埋まっている。

「周囲が0で囲まれている」の判定方法はいろいろある。
自分は本番は違う解法をとっていたが、こっちの隣接８マスをたどるほうが楽かな。

int H,W;
int A[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	
	int ma=-1;
	FOR(y,H) FOR(x,W) if(A[y][x]==1) {
		int L=x,R=x,U=y,D=y,num=0;
		queue<int> Q;
		Q.push(y*1000+x);
		A[y][x]=0;
		
		while(Q.size()) {
			int k=Q.front();
			Q.pop();
			int cy=k/1000,cx=k%1000;
			num++;
			L=min(L,cx);
			R=max(R,cx);
			U=min(U,cy);
			D=max(D,cy);
			
			for(int ty=max(0,cy-1);ty<=min(H-1,cy+1);ty++) {
				for(int tx=max(0,cx-1);tx<=min(W-1,cx+1);tx++) if(A[ty][tx]) {
					A[ty][tx]=0;
					Q.push(ty*1000+tx);
				}
			}
		}
		if(L>0 && R<W-1 && U>0 && D<H-1 && (R-L+1)*(D-U+1)==num) ma=max(ma,num);
	}
	cout<<ma<<endl;
	
}

まとめ

ここまではすんなり解けたのだが。