广东省路桥建设发展有限公司网站知乎软文推广

3197. 包含所有 1 的最小矩形面积 II

题目描述：

给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形，并且满足 grid 中所有的 1 都在这些矩形的内部。

返回这些矩形面积之和的 最小 可能值。

注意，这些矩形可以相接。

$1<=grid.length,grid[i].length<=30$

思路：

观察数据范围，n只有30，估计是$O(n^4)$甚至是$O(n^5)$，所以要想办法暴力

我们只能做到$O(n^2)$的方法去计算一个区域中用一个矩形覆盖的情况

所以要想办法只枚举两次就能把图形分割成三份，情况如下

写代码的时候要仔细，注意下标

class Solution {
public:int n, m, tr[35][35];int cal(int x1, int y1, int x2, int y2){bool fuck = 0;int x_max = 0, x_min = 1e9, y_max = 0, y_min = 1e9;for(int i = x1; i <= x2; ++i){for(int j = y1; j <= y2; ++j){if(tr[i][j]){fuck = 1;x_max = max(x_max, i);x_min = min(x_min, i);y_max = max(y_max, j);y_min = min(y_min, j);}}}if(fuck == 0)return 0;return (x_max - x_min + 1) * (y_max - y_min + 1);}int minimumSum(vector<vector<int>>& num) {n = num.size();m = num[0].size();for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){tr[i][j] = num[i - 1][j - 1];}}int ans = 1e9;for(int i = 1; i <= n; ++i){for(int j = i + 1; j <= n; ++j){ans = min(ans, cal(1,1, i, m) + cal(i + 1, 1, j, m) + cal(j + 1, 1, n, m));}for(int j = 1; j <= m; ++j){ans = min(ans, cal(1, 1, i, j) + cal(i + 1, 1, n, j) + cal(1, j + 1, n, m));ans = min(ans, cal(1, 1, n, j) + cal(1, j + 1, i, m) + cal(i + 1, j + 1, n, m));ans = min(ans, cal(1, 1, i, j) + cal(1, j + 1, i, m) + cal(i + 1, 1, n, m));ans = min(ans, cal(1, 1, i, m) + cal(i + 1, 1, n, j) + cal(i + 1, j + 1, n, m));}}for(int i  = 1; i <= m; ++i){for(int j = i + 1; j <= m; ++j){ans = min(ans, cal(1, 1, n, i) + cal(1, i + 1, n, j) + cal(1, j + 1, n, m));}}return ans;}
};