Explanation: * The 1's at `(0, 0)` and `(0, 2)` are covered by a rectangle of area 3. * The 1 at `(1, 1)` is covered by a rectangle of area 1. * The 1 at `(1, 3)` is covered by a rectangle of area 1.

Constraints

1 <= grid.length, grid[i].length <= 30
grid[i][j] is either 0 or 1.
The input is generated such that there are at least three 1's in grid.

Solution

Method 1 – Brute Force All Rectangle Partitions (for Small Grids)

Intuition

We need to cover all 1's in the grid with 3 non-overlapping rectangles of non-zero area, minimizing the total area. For small grids, we can brute-force all possible ways to partition the grid into 3 rectangles, check if all 1's are covered, and compute the minimum area sum.

Approach

For each possible way to split the grid into 3 rectangles (by vertical and/or horizontal cuts), enumerate all possible rectangles.
For each combination of 3 rectangles, check:
- All rectangles have non-zero area.
- Rectangles do not overlap.
- All 1's in the grid are covered by at least one rectangle.
Compute the sum of the areas for valid combinations and track the minimum.
Return the minimum area sum found.

Code

[{"language":"C++","code":"class Solution {\npublic:\n  int minimumSum(vector<vector<int>>& grid) {\n    int m = grid.size(), n = grid[0].size();\n    vector<pair<int,int>> ones;\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j)\n        if (grid[i][j]) ones.emplace_back(i, j);\n    if (ones.empty()) return 0;\n    int ans = numeric_limits<int>::max();\n\n    for (int r1 = 0; r1 < m; ++r1)\n      for (int r2 = r1; r2 < m; ++r2)\n        for (int c1 = 0; c1 < n; ++c1)\n          for (int c2 = c1; c2 < n; ++c2) {\n            unordered_set<int> rect1;\n            for (int i = r1; i <= r2; ++i)\n              for (int j = c1; j <= c2; ++j)\n                rect1.insert(i * n + j);\n            bool covers1 = false;\n            for (auto &p : ones) if (rect1.count(p.first * n + p.second)) { covers1 = true; break; }\n            if (!covers1) continue;\n\n            for (int rr1 = 0; rr1 < m; ++rr1)\n              for (int rr2 = rr1; rr2 < m; ++rr2)\n                for (int cc1 = 0; cc1 < n; ++cc1)\n                  for (int cc2 = cc1; cc2 < n; ++cc2) {\n                    unordered_set<int> rect2;\n                    bool overlap = false;\n                    for (int i = rr1; i <= rr2 && !overlap; ++i)\n

Related Tags

Continue Practicing