本文涉及知识点
数学
LeetCode3197. 包含所有 1 的最小矩形面积 II
给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形，并且满足 grid 中所有的 1 都在这些矩形的内部。
返回这些矩形面积之和的 最小 可能值。
注意，这些矩形可以相接。
示例 1：
输入： grid = [[1,0,1],[1,1,1]]
输出： 5
解释：
位于 (0, 0) 和 (1, 0) 的 1 被一个面积为 2 的矩形覆盖。
位于 (0, 2) 和 (1, 2) 的 1 被一个面积为 2 的矩形覆盖。
位于 (1, 1) 的 1 被一个面积为 1 的矩形覆盖。
示例 2：
输入： grid = [[1,0,1,0],[0,1,0,1]]
输出： 5
解释：
位于 (0, 0) 和 (0, 2) 的 1 被一个面积为 3 的矩形覆盖。
位于 (1, 1) 的 1 被一个面积为 1 的矩形覆盖。
位于 (1, 3) 的 1 被一个面积为 1 的矩形覆盖。
提示：
1 <= grid.length, grid[i].length <= 30
grid[i][j] 是 0 或 1。
输入保证 grid 中至少有三个 1 。
数学
我们假设某个最优解，包括左上1 的为rect1，包括右下1的矩形为rect2，另外一个矩形为rect3。我们将整个网格水平、竖直划分成3$\times$3 共9块。
第一块是：左上角是(0,0)，右下角是rect1的右下角。
第二块是：左上角是rect2的左上角，右下角是网格右下角。
rect3可能站4块，也可能占3块，也可能占2块，也可能占一块。占4块包括所有占2块，占2块包括所有占1块。
下图的红色并是各种可能。
我们将其转化为网格的大矩形中寻找包括所有1的最小矩形。
四种情况：
一，三竖。
二，三横。
三，一竖二横。
四，一横二竖。
rect2 四种情况全部是3格，rect1 前两种情况是三格，后两种情况是二格。
预处理
各矩形包括全部1的最小矩形的面积，如果不包括1，返回1000。
旧代码
需要枚举4个坐标，非常容易出错。代码通过不了，只能通过部分样例。继续调试时间成本太高。
class Solution {
public:
int minimumSum(vector<vector<int>>& grid) {
m_r = grid.size();
m_c = grid[0].size();
memset(m_area, 1, sizeof(m_area));
for (int r1 = 0; r1 < m_r; r1++) {
for (int c1 = 0; c1 < m_c; c1++) {
for (int r2 = r1; r2 < m_r; r2++) {
for (int c2 = c1; c2 < m_c; c2++) {
Init(grid, r1, r2, c1, c2);
}
}
}
}
for (int r1 = 0; r1 < m_r; r1++) {
for (int c1 = 0; c1 < m_c; c1++) {
if (0 == grid[r1][c1]) { continue; }
for (int r2 = r1 + 1; r2 < m_r; r2++) {
for (int c2 = 0; c2 < m_c; c2++) {
Do(r1, r2, c1, c2);
}
}
for (int c2 = c1 + 1; c2 < m_c; c2++) {
for (int r2 = 0; r2 < m_r; r2++) {
Do(r1, r2, c1, c2);
}
}
}
}
return m_ans;
}
void Do( int r1, int r2, int c1, int c2) {
//三横
m_ans = min(m_ans, Area(0,r1,0,m_c - 1) + Area(r1 + 1,r2 - 1,0,m_c - 1) + Area(r2,m_r - 1,0,m_c - 1));
//三竖
m_ans = min(m_ans, Area(0,m_r - 1,0,c1) + Area(0, m_r - 1, c1 + 1,c2 - 1) + Area(0, m_r - 1, c2,m_c - 1));
//一长度2的横，二长度3的竖
m_ans = min(m_ans, Area(0,r1,0,c2 - 1) + Area(r1 + 1,c2 - 1,0,c2 - 1) + Area(0,m_r - 1,c2,m_c - 1));
//一长度为2的竖，二长度为3横
m_ans = min(m_ans, Area(0,r2 - 1,0,c1) + Area(0,r2 - 1,c1 + 1,m_c - 1) + Area(r2,m_r - 1,0,m_c - 1));
//一长度3的横，二长度2的竖
m_ans = min(m_ans, Area(0, r1, 0, m_c - 1) + Area(r1 + 1, c2 - 1, 0, c2 - 1) + Area(r1+1, m_r - 1, c2, m_c - 1));
//一长度为3的竖，二长度为2横
m_ans = min(m_ans, Area(0, m_r - 1, 0, c1) + Area(0, r2 - 1, c1 + 1, m_c - 1) + Area(r2, m_r - 1, c1+1, m_c - 1));
}
int Area(int r1, int r2, int c1, int c2) {
if ((r1 < 0) || (r1 >= m_r)) { return m_iNotMay; }
if ((r2 < 0) || (r2 >= m_r)) { return m_iNotMay; }
if ((c1 < 0) || (c2 >= m_c)) { return m_iNotMay; }
if ((c2 < 0) || (c2 >= m_c)) { return m_iNotMay; }
return m_area[r1][r2][c1][c2];
}
void Init(const vector<vector<int>>& grid,int r1,int r2,int c1,int c2) {
int right = -1, bottom = -1, left = 2000, top = 2000;
for (int r = r1; r <= r2; r++) {
for (int c = c1; c <=c2; c++) {
if (grid[r][c]) {
right = max(right, c);
bottom = max(bottom, r);
left = min(left, c);
top = min(top, r);
}
}
}
m_area[r1][r2][c1][c2] = (right - left + 1) * (bottom - top + 1);
}
const int m_iNotMay = 1000'000;
int m_area[30][30][30][30];
int m_r, m_c;
int m_ans = 1000'000;
};
新代码
六种情况，只需要枚举两个变量。如果用预处理，时间复杂度O(nm)或O(nn)或O(mm)。
不用预处理时间复杂度:O(nmnn)也能过，故不用预处理。
class Solution {
public:
int minimumSum(vector<vector<int>>& grid) {
m_r = grid.size();
m_c = grid[0].size();
auto Area =[&]( int r1, int r2, int c1, int c2) {
int right = -1, bottom = -1, left = 2000, top = 2000;
for (int r = r1; r <= r2; r++) {
for (int c = c1; c <= c2; c++) {
if (grid[r][c]) {
right = max(right, c);
bottom = max(bottom, r);
left = min(left, c);
top = min(top, r);
}
}
}
return (right - left + 1) * (bottom - top + 1);
};
{//三横
for (int r1 = 0; r1 < m_r; r1++) {
for (int r2 = r1 + 2; r2 < m_r; r2++) {
m_ans = min(m_ans, Area(0,r1,0,m_c-1)+Area(r1+1,r2-1,0,m_c-1) + Area(r2,m_r-1,0,m_c-1));
}
}
}
{//三竖
for (int c1 = 0; c1 < m_c; c1++) {
for (int c2 = c1 + 2; c2 < m_c; c2++) {
m_ans = min(m_ans, Area(0, m_r-1, 0,c1) + Area(0, m_r - 1, c1+1,c2-1) + Area(0, m_r - 1, c2,m_c-1));
}
}
}
for (int r = 0; r + 1 < m_r; r++) {
for (int c = 0; c + 1 < m_c; c++) {
//上一下二
m_ans = min(m_ans, Area(0, r, 0, m_c - 1) + Area(r + 1,m_r - 1, 0, c) + Area(r + 1, m_r - 1, c+1, m_c - 1));
//上二下一
m_ans = min(m_ans, Area(0, r, 0, c) + Area(0, r, c+1, m_c-1) + Area(r + 1, m_r - 1, 0, m_c - 1));
//左一右二
m_ans = min(m_ans, Area(0, m_r - 1, 0, c) + Area(0, r, c + 1, m_c - 1) + Area(r+1, m_r - 1, c + 1, m_c - 1));
//左二右一
m_ans = min(m_ans, Area(0, r, 0, c) + Area(r+1,m_r-1, 0, c) + Area(0, m_r - 1, c + 1, m_c - 1));
}
}
return m_ans;
}
const int m_iNotMay = 1000'000;
int m_r, m_c;
int m_ans = 1000'000;
};
代码
template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
Assert::AreEqual(t1, t2);
}
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
Assert::AreEqual(v1.size(), v2.size());
for (int i = 0; i < v1.size(); i++)
{
Assert::AreEqual(v1[i], v2[i]);
}
}
template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
sort(vv1.begin(), vv1.end());
sort(vv2.begin(), vv2.end());
Assert::AreEqual(vv1.size(), vv2.size());
for (int i = 0; i < vv1.size(); i++)
{
AssertEx(vv1[i], vv2[i]);
}
}
namespace UnitTest
{
vector<vector<int>> grid;
TEST_CLASS(UnitTest)
{
public:
TEST_METHOD(TestMethod00)
{
grid = { {1,0,1},{1,1,1} };
auto res = Solution().minimumSum(grid);
AssertEx(5, res);
}
TEST_METHOD(TestMethod01)
{
grid = { {1,0,1,0},{0,1,0,1} };
auto res = Solution().minimumSum(grid);
AssertEx(5, res);
}
TEST_METHOD(TestMethod02)
{
grid = { {0,1},{1,1} };
auto res = Solution().minimumSum(grid);
AssertEx(3, res);
}
TEST_METHOD(TestMethod03)
{
grid = { {0,0,0},{0,1,0},{0,1,1},{0,0,0} };
auto res = Solution().minimumSum(grid);
AssertEx(3, res);
}
};
}
