学网站建设需要几年,vip视频解析网站怎么做的,wordpress官方模板,上海软件开发工程师工资一般多少3197. 包含所有 1 的最小矩形面积 II
题目描述#xff1a;
给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形#xff0c;并且满足 grid 中所有的 1 都在这些矩形的内部。
返回这些矩形面积之和的 最小 可能值。
注意…3197. 包含所有 1 的最小矩形面积 II
题目描述
给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形并且满足 grid 中所有的 1 都在这些矩形的内部。
返回这些矩形面积之和的 最小 可能值。
注意这些矩形可以相接。 1 g r i d . l e n g t h , g r i d [ i ] . l e n g t h 30 1 grid.length, grid[i].length 30 1grid.length,grid[i].length30
思路
观察数据范围n只有30估计是 O ( n 4 ) O(n^4) O(n4)甚至是 O ( n 5 ) O(n^5) O(n5)所以要想办法暴力
我们只能做到 O ( n 2 ) O(n^2) O(n2)的方法去计算一个区域中用一个矩形覆盖的情况
所以要想办法只枚举两次就能把图形分割成三份情况如下 写代码的时候要仔细注意下标
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(vectorvectorint 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;}
};
