3197. Find the Minimum Area to Cover All Ones II
思路 :
就切切切
先切成两个矩形
再把其中一个矩形切成另外两个矩形
看最小的三个矩形面积是多少
然后可以水平切或是垂直切
切切切切切切切切切切切
因为题目限制边长不超过30
就暴力解救好
golang code :
func minimumSum(grid [][]int) int {
n, m := len(grid), len(grid[0])
ans := math.MaxInt64
for i := 0; i < n; i++ {
area1, area2, cutPos := minimumArea(grid, 0, i, 0, m), minimumArea(grid, i,
n, 0, m), i
tmp := [4][3]int{}
tmp[0] = twoRectangleH(grid, 0, cutPos, 0, m) //area1水平切
tmp[1] = twoRectangleV(grid, 0, cutPos, 0, m) //area1垂直切
tmp[2] = twoRectangleH(grid, cutPos, n, 0, m) //area2水平切
tmp[3] = twoRectangleV(grid, cutPos, n, 0, m) //area2垂直切
ans = min(ans, area2+tmp[0][0]+tmp[0][1])
ans = min(ans, area2+tmp[1][0]+tmp[1][1])
ans = min(ans, area1+tmp[2][0]+tmp[2][1])
ans = min(ans, area1+tmp[3][0]+tmp[3][1])
}
for i := 0; i < m; i++ {
area1, area2, cutPos := minimumArea(grid, 0, n, 0, i), minimumArea(grid, 0,
n, i, m), i
tmp := [4][3]int{}
tmp[0] = twoRectangleH(grid, 0, n, 0, cutPos) //area3水平切
tmp[1] = twoRectangleV(grid, 0, n, 0, cutPos) //area3垂直切
tmp[2] = twoRectangleH(grid, 0, n, cutPos, m) //area4水平切
tmp[3] = twoRectangleV(grid, 0, n, cutPos, m) //area4垂直切
ans = min(ans, area2+tmp[0][0]+tmp[0][1])
ans = min(ans, area2+tmp[1][0]+tmp[1][1])
ans = min(ans, area1+tmp[2][0]+tmp[2][1])
ans = min(ans, area1+tmp[3][0]+tmp[3][1])
}
return ans
}
func twoRectangleV(grid [][]int, n1, n2, m1, m2 int) [3]int {
minArea, area1, area2, c := math.MaxInt64, 0, 0, -1
// 垂直切
for j := m1; j < m2; j++ {
left := minimumArea(grid, n1, n2, m1, j)
right := minimumArea(grid, n1, n2, j, m2)
tmp := left + right
if tmp <= minArea {
area1, area2 = left, right
minArea = tmp
c = j
}
}
return [3]int{area1, area2, c}
}
func twoRectangleH(grid [][]int, n1, n2, m1, m2 int) [3]int {
minArea, area1, area2, r := math.MaxInt64, 0, 0, -1
// 水平切
for i := n1; i < n2; i++ {
up := minimumArea(grid, n1, i, m1, m2)
down := minimumArea(grid, i, n2, m1, m2)
tmp := up + down
if tmp <= minArea {
area1, area2 = up, down
minArea = tmp
r = i
}
}
return [3]int{area1, area2, r}
}
func minimumArea(grid [][]int, n1, n2, m1, m2 int) int {
b, u, l, r := n1-1, n2, m2, m1-1
for i := n1; i < n2; i++ {
for j := m1; j < m2; j++ {
if grid[i][j] == 1 {
b = max(b, i)
u = min(u, i)
l = min(l, j)
r = max(r, j)
}
}
}
return (r - l + 1) * (b - u + 1)
}