LeetCode Weekly Contest 403 : 3197. Find the Minimum Area to Cover All Ones II

だいぶ典型な気はする。
https://leetcode.com/problems/find-the-minimum-area-to-cover-all-ones-ii/description/

問題

H*Wの白黒のグリッドが与えられる。
ここに、互いに共通部分を持たない3つの矩形領域を設定し、黒マスをすべて覆いたい。
矩形領域の面積の和の最小値を求めよ。

解法

矩形範囲内において、1つの矩形で内部の黒マスを全部覆うときの面積の最小値は典型的なDPでO(H^2*W^2)で計算できる。
あとはグリッドを3分割するやり方を総当たりしよう。

• 縦に三分割する
• 横に三分割する
• 縦に二分割した後、左側または右側のいずれかを縦に二分割する
• 横に二分割した後、上側または下側のいずれかを横に二分割する

int H,W;
int A[31][31];
int coverall[31][31][31][31];

int num(int L,int R,int U,int D) {
	return A[R][D]-A[L][D]-A[R][U]+A[L][U];
}

int cover(int L,int R,int U,int D) {
	int n=num(L,R,U,D);
	if(n==0) return 0;
	if(coverall[L][R][U][D]>=0) return coverall[L][R][U][D];
	
	int ret=(R-L)*(D-U);
	if(num(L+1,R,U,D)==n) ret=min(ret,cover(L+1,R,U,D));
	if(num(L,R-1,U,D)==n) ret=min(ret,cover(L,R-1,U,D));
	if(num(L,R,U+1,D)==n) ret=min(ret,cover(L,R,U+1,D));
	if(num(L,R,U,D-1)==n) ret=min(ret,cover(L,R,U,D-1));
	return coverall[L][R][U][D]=ret;
	
}

class Solution {
public:
    int minimumSum(vector<vector<int>>& grid) {
        MINUS(coverall);
        H=grid.size();
        W=grid[0].size();
        int y,x,a1,a2;
        FOR(y,H) FOR(x,W) {
			A[y+1][x+1]=A[y+1][x]+A[y][x+1]-A[y][x]+grid[y][x];
		}
        int mi=1<<30;
        for(a2=1;a2<H;a2++) for(a1=1;a1<a2;a1++) {
			mi=min(mi,cover(0,a1,0,W)+cover(a1,a2,0,W)+cover(a2,H,0,W));
		}
        for(a2=1;a2<W;a2++) for(a1=1;a1<a2;a1++) {
			mi=min(mi,cover(0,H,0,a1)+cover(0,H,a1,a2)+cover(0,H,a2,W));
		}
		
		for(y=1;y<H;y++) {
			for(x=1;x<W;x++) {
				mi=min(mi,cover(0,y,0,W)+cover(y,H,0,x)+cover(y,H,x,W));
				mi=min(mi,cover(0,y,0,x)+cover(0,y,x,W)+cover(y,H,0,W));
				mi=min(mi,cover(0,H,0,x)+cover(0,y,x,W)+cover(y,H,x,W));
				mi=min(mi,cover(0,y,0,x)+cover(y,H,0,x)+cover(0,H,x,W));
				
			}
		}
        return mi;
        
        
        
        
    }
};

まとめ

難易度7でもいい気がするけど…。
LeetCodeで出にくいタイプのものんだいは難易度高めに出るのかな。