# Find the Minimum Area to Cover All Ones II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-minimum-area-to-cover-all-ones-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-minimum-area-to-cover-all-ones-ii
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Matrix
---
## Problem
You are given a 2D **binary** array `grid`. You need to find 3 **non-overlapping** rectangles having **non-zero** areas with horizontal and vertical sides such that all the 1's in `grid` lie inside these rectangles.

Return the **minimum** possible sum of the area of these rectangles.

**Note** that the rectangles are allowed to touch.

**Example 1:**

**Input:** grid = \[\[1,0,1\],\[1,1,1\]\]

**Output:** 5

**Explanation:**

![](https://assets.glich.co/dsa/find-the-minimum-area-to-cover-all-ones-ii/image0.png)

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

**Example 2:**

**Input:** grid = \[\[1,0,1,0\],\[0,1,0,1\]\]

**Output:** 5

**Explanation:**

![](https://assets.glich.co/dsa/find-the-minimum-area-to-cover-all-ones-ii/image1.png)

* 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`.

# Approaches
## Brute-force Enumeration of Partitions
This approach exhaustively checks every possible way to partition the grid into three non-overlapping rectangles. There are six fundamental patterns for such a partition: two parallel vertical cuts, two parallel horizontal cuts, and four 'T'-shaped configurations. The algorithm iterates through all possible positions for these cuts. For each potential partition, it calculates the area of the bounding box for the '1's within each of the three resulting rectangular regions. The sum of these three areas is a candidate for the minimum total area. By checking all possibilities, we can find the global minimum.
**Time:** O(m^2 * n^2). The dominant part is handling the T-shaped cuts. There are O(m*n) possible cut intersections. For each, we call `getArea` three times. Each `getArea` call can take up to O(m*n) time in the worst case. This leads to a total complexity of O(m*n * m*n) = O(m^2 * n^2). The parallel cut cases have complexities of O(m*n^3) and O(n*m^3), which are lower for square-like grids. · **Space:** O(1) besides the input grid storage.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find the correct answer because it checks all possible partition structures.
**Cons:** The time complexity is high due to redundant calculations.; The `getArea` function is called repeatedly for overlapping subgrids, leading to inefficiency.
### Explanation
The core of this method is a helper function, `getArea(r1, c1, r2, c2)`, which calculates the minimum bounding box area for all `1`s within a specified rectangular subgrid. This function works by iterating through the cells of the subgrid to find the minimum and maximum row and column indices of the `1`s.

The main logic then explores all six partitioning schemes:

1.  **Two Vertical Cuts:** We use two nested loops to iterate through all possible positions for two vertical lines, `c1` and `c2`. These lines divide the grid into three vertical strips: `cols 0..c1-1`, `cols c1..c2-1`, and `cols c2..n-1`. We calculate the area for each strip and sum them up.

2.  **Two Horizontal Cuts:** This is analogous to the vertical case, but we iterate through two horizontal lines, `r1` and `r2`, to create three horizontal strips.

3.  **T-Shaped Cuts:** A T-shaped partition is formed by one main cut that spans the grid, and a second, perpendicular cut that splits one of the two resulting sub-rectangles. We can iterate through all possible intersection points `(r, c)` of a horizontal and a vertical line. This gives us four ways to form three rectangles (e.g., one rectangle on the left of `c`, and two rectangles on the right of `c` separated by `r`). We check all four such configurations for each `(r, c)` pair.

For every partition, we ensure that each of the three rectangles contains at least one '1' (has a non-zero area) before considering its total area as a potential minimum.

```java
class Solution {
    private int[][] grid;
    private int m, n;

    public int minimumArea(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        long minArea = Long.MAX_VALUE;

        // Case 1: Two vertical cuts
        for (int c1 = 1; c1 < n; c1++) {
            for (int c2 = c1 + 1; c2 < n; c2++) {
                long area1 = getArea(0, 0, m - 1, c1 - 1);
                long area2 = getArea(0, c1, m - 1, c2 - 1);
                long area3 = getArea(0, c2, m - 1, n - 1);
                if (area1 > 0 && area2 > 0 && area3 > 0) {
                    minArea = Math.min(minArea, area1 + area2 + area3);
                }
            }
        }

        // Case 2: Two horizontal cuts
        for (int r1 = 1; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                long area1 = getArea(0, 0, r1 - 1, n - 1);
                long area2 = getArea(r1, 0, r2 - 1, n - 1);
                long area3 = getArea(r2, 0, m - 1, n - 1);
                if (area1 > 0 && area2 > 0 && area3 > 0) {
                    minArea = Math.min(minArea, area1 + area2 + area3);
                }
            }
        }

        // Cases 3-6: T-shaped cuts
        for (int c = 1; c < n; c++) {
            for (int r = 1; r < m; r++) {
                // Config 1: Left, Top-Right, Bottom-Right
                long a1 = getArea(0, 0, m - 1, c - 1);
                long a2 = getArea(0, c, r - 1, n - 1);
                long a3 = getArea(r, c, m - 1, n - 1);
                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);

                // Config 2: Right, Top-Left, Bottom-Left
                a1 = getArea(0, c, m - 1, n - 1);
                a2 = getArea(0, 0, r - 1, c - 1);
                a3 = getArea(r, 0, m - 1, c - 1);
                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);

                // Config 3: Top, Bottom-Left, Bottom-Right
                a1 = getArea(0, 0, r - 1, n - 1);
                a2 = getArea(r, 0, m - 1, c - 1);
                a3 = getArea(r, c, m - 1, n - 1);
                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);

                // Config 4: Bottom, Top-Left, Top-Right
                a1 = getArea(r, 0, m - 1, n - 1);
                a2 = getArea(0, 0, r - 1, c - 1);
                a3 = getArea(0, c, r - 1, n - 1);
                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);
            }
        }

        return (int) minArea;
    }

    private long getArea(int r1, int c1, int r2, int c2) {
        int minR = m, maxR = -1, minC = n, maxC = -1;
        boolean foundOne = false;
        for (int i = r1; i <= r2; i++) {
            for (int j = c1; j <= c2; j++) {
                if (grid[i][j] == 1) {
                    foundOne = true;
                    minR = Math.min(minR, i);
                    maxR = Math.max(maxR, i);
                    minC = Math.min(minC, j);
                    maxC = Math.max(maxC, j);
                }
            }
        }
        if (!foundOne) return 0;
        return (long) (maxR - minR + 1) * (maxC - minC + 1);
    }
}
```
### Algorithm
1. Implement a helper function `getArea(r1, c1, r2, c2)` that computes the area of the smallest bounding box covering all '1's within the subgrid from `(r1, c1)` to `(r2, c2)`. This function iterates through all cells in the subgrid. If no '1's are found, it returns 0.
2. Initialize a variable `minTotalArea` to a very large value.
3. Systematically check all 6 ways to partition a rectangle into three smaller rectangles:
    - **Two vertical cuts:** Iterate through all possible pairs of vertical cut lines, `c1` and `c2`. This creates three vertical rectangular regions. Calculate the area for each region using `getArea`. If all three areas are non-zero, update `minTotalArea` with their sum.
    - **Two horizontal cuts:** Similarly, iterate through all pairs of horizontal cut lines, `r1` and `r2`, and do the same.
    - **Four T-shaped cuts:** Iterate through a vertical cut `c` and a horizontal cut `r`. These two cuts divide the grid into four quadrants. By combining three of these quadrants in different ways, we can form four distinct T-shaped partitions. For each of these four configurations, calculate the areas of the three rectangles and update `minTotalArea` if they are all non-zero. The four configurations are:
        a. Left rectangle, top-right rectangle, bottom-right rectangle.
        b. Right rectangle, top-left rectangle, bottom-left rectangle.
        c. Top rectangle, bottom-left rectangle, bottom-right rectangle.
        d. Bottom rectangle, top-left rectangle, top-right rectangle.
4. After checking all possible partitions, `minTotalArea` will hold the minimum possible sum of areas.

## Optimized Partitioning with Precomputation
This approach significantly optimizes the brute-force method by avoiding redundant calculations through precomputation and dynamic programming-like techniques. We first precompute the bounding box areas for all possible contiguous vertical and horizontal strips of the grid. This allows for O(1) area lookups for the parallel cut partitions. For the more complex T-shaped partitions, we iterate through the primary cut line. For each primary cut, instead of naively calculating the areas of the two smaller rectangles, we use an efficient method to find the optimal secondary cut, reducing the complexity for these cases as well.
**Time:** O(mn(m+n)). Precomputation takes O(m*n^2 + n*m^2). The parallel cut checks take O(m^2 + n^2). The T-cut checks take O(n * (m*n)) for vertical primary cuts and O(m * (m*n)) for horizontal primary cuts. The dominant part is the T-cut evaluation, leading to a total complexity of O(m*n^2 + n*m^2). · **Space:** O(m^2 + n^2) to store the precomputed area tables for horizontal and vertical strips.
**Pros:** Much more efficient than the brute-force approach.; Handles the given constraints (m, n <= 30) very quickly.
**Cons:** More complex to implement due to precomputation steps and more intricate loop structures.; Requires additional space for the precomputed tables.
### Explanation
The main idea is to reduce the time spent inside the loops by pre-calculating necessary values.

**Precomputation:**
First, we compute `areaCol[c1][c2]`, the bounding box area for columns `c1` to `c2`. We can do this in O(n^2) time after an initial O(m*n) scan to find the vertical extents of '1's in each column. Similarly, we compute `areaRow[r1][r2]` in O(m^2) time.

**Partition Evaluation:**
- **Parallel Cuts:** With the precomputed tables, finding the minimum area for two parallel vertical cuts takes just O(n^2) time, as each partition's area is a sum of three O(1) table lookups. Similarly, horizontal cuts take O(m^2).

- **T-Shaped Cuts:** Let's analyze one configuration: a vertical cut at `c` separating a left rectangle from a right part, which is then split horizontally at `r`. We iterate `c` from `1` to `n-1`. The area of the left rectangle is simply `areaCol[0][c-1]`. For the right part (`grid[:, c:]`), we need to find the best horizontal split `r`. We can do this efficiently. For the fixed `c`, we can compute an array `topRightArea[r]` (area for `grid[0..r-1][c..n-1]`) for all `r` in O(m*n) time by incrementally building the bounding box. Similarly, we compute `bottomRightArea[r]` (area for `grid[r..m-1][c..n-1]`). Then, we iterate through `r` in O(m) to find the minimum sum `topRightArea[r] + bottomRightArea[r]`. The total time for this T-cut configuration becomes O(n * (m*n + m)) = O(m*n^2). We apply the same logic to all T-cut cases.

This strategy reduces the overall complexity from O(m^2*n^2) to O(mn(m+n)), which is a significant improvement.

```java
class Solution {
    public int minimumArea(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        long minArea = Long.MAX_VALUE;

        // Calculate areas for all vertical and horizontal strips
        long[][] areaCol = precomputeArea(grid, m, n, true);
        long[][] areaRow = precomputeArea(grid, m, n, false);

        // Case 1: Two vertical cuts
        for (int c1 = 1; c1 < n; c1++) {
            for (int c2 = c1 + 1; c2 < n; c2++) {
                long a1 = areaCol[0][c1 - 1];
                long a2 = areaCol[c1][c2 - 1];
                long a3 = areaCol[c2][n - 1];
                if (a1 > 0 && a2 > 0 && a3 > 0) {
                    minArea = Math.min(minArea, a1 + a2 + a3);
                }
            }
        }

        // Case 2: Two horizontal cuts
        for (int r1 = 1; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                long a1 = areaRow[0][r1 - 1];
                long a2 = areaRow[r1][r2 - 1];
                long a3 = areaRow[r2][m - 1];
                if (a1 > 0 && a2 > 0 && a3 > 0) {
                    minArea = Math.min(minArea, a1 + a2 + a3);
                }
            }
        }

        // Cases 3-6: T-shaped cuts
        for (int c = 1; c < n; c++) {
            long leftArea = areaCol[0][c - 1];
            long rightArea = areaCol[c][n - 1];
            long vSplitRight = minAreaFor2Rects(grid, 0, c, m - 1, n - 1, true);
            long vSplitLeft = minAreaFor2Rects(grid, 0, 0, m - 1, c - 1, true);
            if (leftArea > 0 && vSplitRight > 0) minArea = Math.min(minArea, leftArea + vSplitRight);
            if (rightArea > 0 && vSplitLeft > 0) minArea = Math.min(minArea, rightArea + vSplitLeft);
        }

        for (int r = 1; r < m; r++) {
            long topArea = areaRow[0][r - 1];
            long bottomArea = areaRow[r][m - 1];
            long hSplitBottom = minAreaFor2Rects(grid, r, 0, m - 1, n - 1, false);
            long hSplitTop = minAreaFor2Rects(grid, 0, 0, r - 1, n - 1, false);
            if (topArea > 0 && hSplitBottom > 0) minArea = Math.min(minArea, topArea + hSplitBottom);
            if (bottomArea > 0 && hSplitTop > 0) minArea = Math.min(minArea, bottomArea + hSplitTop);
        }

        return (int) minArea;
    }

    private long[][] precomputeArea(int[][] grid, int m, int n, boolean isVertical) {
        int dim1 = isVertical ? n : m;
        int dim2 = isVertical ? m : n;
        long[][] area = new long[dim1][dim1];

        for (int i = 0; i < dim1; i++) {
            int minR = dim2, maxR = -1, minC = dim1, maxC = -1;
            boolean hasOne = false;
            for (int j = i; j < dim1; j++) {
                int currentMinR = dim2, currentMaxR = -1;
                for (int k = 0; k < dim2; k++) {
                    if ((isVertical && grid[k][j] == 1) || (!isVertical && grid[j][k] == 1)) {
                        currentMinR = Math.min(currentMinR, k);
                        currentMaxR = Math.max(currentMaxR, k);
                    }
                }
                if (currentMaxR != -1) {
                    hasOne = true;
                    minR = Math.min(minR, currentMinR);
                    maxR = Math.max(maxR, currentMaxR);
                }
                if (hasOne) {
                    area[i][j] = (long)(maxR - minR + 1) * (j - i + 1);
                }
            }
        }
        return area;
    }

    private long minAreaFor2Rects(int[][] grid, int r1, int c1, int r2, int c2, boolean verticalSplit) {
        long minArea = Long.MAX_VALUE;
        if (verticalSplit) { // Split horizontally
            for (int r = r1 + 1; r <= r2; r++) {
                long a1 = getArea(grid, r1, c1, r - 1, c2);
                long a2 = getArea(grid, r, c1, r2, c2);
                if (a1 > 0 && a2 > 0) minArea = Math.min(minArea, a1 + a2);
            }
        } else { // Split vertically
            for (int c = c1 + 1; c <= c2; c++) {
                long a1 = getArea(grid, r1, c1, r2, c - 1);
                long a2 = getArea(grid, r1, c, r2, c2);
                if (a1 > 0 && a2 > 0) minArea = Math.min(minArea, a1 + a2);
            }
        }
        return minArea == Long.MAX_VALUE ? 0 : minArea;
    }

    private long getArea(int[][] grid, int r1, int c1, int r2, int c2) {
        int minR = grid.length, maxR = -1, minC = grid[0].length, maxC = -1;
        boolean foundOne = false;
        for (int i = r1; i <= r2; i++) {
            for (int j = c1; j <= c2; j++) {
                if (grid[i][j] == 1) {
                    foundOne = true;
                    minR = Math.min(minR, i);
                    maxR = Math.max(maxR, i);
                    minC = Math.min(minC, j);
                    maxC = Math.max(maxC, j);
                }
            }
        }
        if (!foundOne) return 0;
        return (long)(maxR - minR + 1) * (maxC - minC + 1);
    }
}
```
### Algorithm
1. **Precomputation:**
   - Create a table `areaCol[c1][c2]` to store the bounding box area for all '1's in the vertical strip from column `c1` to `c2`. This can be computed in O(m*n + n^2) time.
   - Similarly, create `areaRow[r1][r2]` for horizontal strips in O(m*n + m^2) time.
2. Initialize `minTotalArea` to a very large value.
3. **Case 1 & 2: Parallel cuts.**
   - For two vertical cuts, iterate through `c1` and `c2` (O(n^2) pairs). The total area is `areaCol[0][c1-1] + areaCol[c1][c2-1] + areaCol[c2][n-1]`. This is an O(1) lookup. Update `minTotalArea`.
   - Do the same for two horizontal cuts using `areaRow` (O(m^2) iterations).
4. **Case 3-6: T-shaped cuts.**
   - Consider the case with a primary vertical cut at `c` and a secondary horizontal cut at `r` (e.g., Left + Top-Right + Bottom-Right).
   - Iterate through the primary cut `c` from `1` to `n-1`.
   - The area of the first rectangle (e.g., the left part) is `areaCol[0][c-1]`, which is a precomputed value.
   - For the remaining part (e.g., the right part), we need to find the best horizontal split `r`. Instead of recomputing from scratch, we can efficiently calculate the areas of the top-right and bottom-right parts for all possible `r`'s in O(m*n) time for a fixed `c`.
   - For a fixed `c`, precompute `topRightArea[r]` (area of `grid[0..r-1][c..n-1]`) and `bottomRightArea[r]` (area of `grid[r..m-1][c..n-1]`) for all `r`.
   - Then, iterate `r` from `1` to `m-1` to find the minimum sum `topRightArea[r] + bottomRightArea[r]`.
   - Combine this minimum with the area of the first rectangle to update `minTotalArea`.
   - Apply this optimized logic to all four T-shaped cut configurations.
5. Return `minTotalArea`.

# Solutions
### Java

```java
class Solution {
private
  final int inf = 1 << 30;
private
  int[][] grid;
public
  int minimumSum(int[][] grid) {
    this.grid = grid;
    int m = grid.length;
    int n = grid[0].length;
    int ans = m * n;
    for (int i1 = 0; i1 < m - 1; i1++) {
      for (int i2 = i1 + 1; i2 < m - 1; i2++) {
        ans = Math.min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) +
                                f(i2 + 1, 0, m - 1, n - 1));
      }
    }
    for (int j1 = 0; j1 < n - 1; j1++) {
      for (int j2 = j1 + 1; j2 < n - 1; j2++) {
        ans = Math.min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) +
                                f(0, j2 + 1, m - 1, n - 1));
      }
    }
    for (int i = 0; i < m - 1; i++) {
      for (int j = 0; j < n - 1; j++) {
        ans = Math.min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) +
                                f(i + 1, 0, m - 1, n - 1));
        ans = Math.min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) +
                                f(i + 1, j + 1, m - 1, n - 1));
        ans = Math.min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) +
                                f(0, j + 1, m - 1, n - 1));
        ans = Math.min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) +
                                f(i + 1, j + 1, m - 1, n - 1));
      }
    }
    return ans;
  }
private
  int f(int i1, int j1, int i2, int j2) {
    int x1 = inf, y1 = inf;
    int x2 = -inf, y2 = -inf;
    for (int i = i1; i <= i2; i++) {
      for (int j = j1; j <= j2; j++) {
        if (grid[i][j] == 1) {
          x1 = Math.min(x1, i);
          y1 = Math.min(y1, j);
          x2 = Math.max(x2, i);
          y2 = Math.max(y2, j);
        }
      }
    }
    return (x2 - x1 + 1) * (y2 - y1 + 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumSum(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    int ans = m * n;
    int inf = INT_MAX / 4;
    auto f = [&](int i1, int j1, int i2, int j2) {
      int x1 = inf, y1 = inf;
      int x2 = -inf, y2 = -inf;
      for (int i = i1; i <= i2; i++) {
        for (int j = j1; j <= j2; j++) {
          if (grid[i][j] == 1) {
            x1 = min(x1, i);
            y1 = min(y1, j);
            x2 = max(x2, i);
            y2 = max(y2, j);
          }
        }
      }
      return x1 > x2 || y1 > y2 ? inf : (x2 - x1 + 1) * (y2 - y1 + 1);
    };
    for (int i1 = 0; i1 < m - 1; i1++) {
      for (int i2 = i1 + 1; i2 < m - 1; i2++) {
        ans = min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) +
                           f(i2 + 1, 0, m - 1, n - 1));
      }
    }
    for (int j1 = 0; j1 < n - 1; j1++) {
      for (int j2 = j1 + 1; j2 < n - 1; j2++) {
        ans = min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) +
                           f(0, j2 + 1, m - 1, n - 1));
      }
    }
    for (int i = 0; i < m - 1; i++) {
      for (int j = 0; j < n - 1; j++) {
        ans = min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) +
                           f(i + 1, 0, m - 1, n - 1));
        ans = min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) +
                           f(i + 1, j + 1, m - 1, n - 1));
        ans = min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) +
                           f(0, j + 1, m - 1, n - 1));
        ans = min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) +
                           f(i + 1, j + 1, m - 1, n - 1));
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int: def f(i1: int, j1: int, i2: int, j2: int) -> int: x1 = y1 = inf x2 = y2 = - inf for i in range(i1, i2 + 1): for j in range(j1, j2 + 1): if grid[i][j] == 1: x1 = min(x1, i) y1 = min(y1, j) x2 = max(x2, i) y2 = max(y2, j) return (x2 - x1 + 1) * (y2 - y1 + 1) m, n = len(grid), len(grid[0]) ans = m * n for i1 in range(m - 1): for i2 in range(i1 + 1, m - 1): ans = min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) + f(i2 + 1, 0, m - 1, n - 1), ) for j1 in range(n - 1): for j2 in range(j1 + 1, n - 1): ans = min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) + f(0, j2 + 1, m - 1, n - 1), ) for i in range(m - 1): for j in range(n - 1): ans = min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) + f(i + 1, 0, m - 1, n - 1), ) ans = min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) + f(i + 1, j + 1, m - 1, n - 1), ) ans = min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) + f(0, j + 1, m - 1, n - 1), ) ans = min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) + f(i + 1, j + 1, m - 1, n - 1), ) return ans

```