Codeforces #1058 : Div1 B. Rectangles

順調かと思ったらコーナーケースを落とした…。
https://codeforces.com/contest/2159/problem/B

問題

H*Wの行列が与えられる。各要素は0,1のいずれかである。
ここで有効な矩形領域は、sub-matrixのうち、四つ角の要素がいずれも1であることとする。
元の行列の各要素について、その要素を含む有効なsub-matrixのうち最小のサイズを答えよ。

解法

H≦Wとする。
矩形領域の上端と下端を総当たりし、列を平面走査の要領で探索しよう。
そうすればO(H^2*W)で解ける。

H＞Wの場合はあらかじめ90度回転させればよい。

int T,H,W;
vector<string> S;
vector<vector<int>> R;
int swapped;



//xy入れ替え
vector<string> flip(vector<string> S) {
	vector<string> T;
	int H=S.size(),W=S[0].size(),x,y;
	FOR(x,W) T.push_back(string(H,' '));
	FOR(y,H) FOR(x,W) T[x][y]=S[y][x]; //left
	return T;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		S.resize(H);
		FOR(y,H) cin>>S[y];
		swapped=0;
		if(H>W) {
			S=flip(S);
			swap(H,W);
			swapped=1;
		}
		R.clear();
		R.resize(H);
		FOR(y,H) R[y].resize(W,1<<30);
		auto TR=R;
		
		int y1,y2;
		FOR(y2,H) {
			FOR(y,y2+1) FOR(x,W) TR[y][x]=1<<30;
			
			FOR(y1,y2) {
				int pre=-1;
				FOR(x,W) if(S[y1][x]=='1'&&S[y2][x]=='1') {
					if(pre!=-1) {
						r=(y2-y1+1)*(x-pre+1);
						for(k=pre;k<=x;k++) TR[y1][k]=min(TR[y1][k],r);
					}
					pre=x;
				}
			}
			FOR(y,y2+1) {
				FOR(x,W) {
					if(y) TR[y][x]=min(TR[y][x],TR[y-1][x]);
					R[y][x]=min(R[y][x],TR[y][x]);
				}
			}
		}
		
		FOR(y,H) {
			FOR(x,W) if(R[y][x]>1<<20) R[y][x]=0;
		}
		
		if(swapped==0) {
			FOR(y,H) {
				FOR(x,W) cout<<R[y][x]<<" ";
				cout<<endl;
			}
		}
		else {
			FOR(x,W) {
				FOR(y,H) cout<<R[y][x]<<" ";
				cout<<endl;
			}
		}
	}
}

まとめ

最大ケースでTLEしてた…。