cpp 解法, 执行用时: 48 ms, 内存消耗: 45.4 MB, 提交时间: 2024-06-28 17:52:42

class Solution {
    // 顺时针旋转矩阵 90°
    vector<vector<int>> rotate(vector<vector<int>> a) {
        int m = a.size(), n = a[0].size();
        vector<vector<int>> b(n, vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                b[j][m - 1 - i] = a[i][j];
            }
        }
        return b;
    }

    vector<vector<int>> minimumArea(vector<vector<int>>& a) {
        int m = a.size(), n = a[0].size();
        // f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        vector<tuple<int, int, int>> border(n + 1, {-1, -1, -1});
        for (int i = 0; i < m; i++) {
            int left = -1, right = 0;
            for (int j = 0; j < n; j++) {
                if (a[i][j]) {
                    if (left < 0) {
                        left = j;
                    }
                    right = j;
                }
                auto& [pre_top, pre_left, pre_right] = border[j];
                if (left < 0) { // 这一排目前全是 0
                    f[i + 1][j + 1] = f[i][j + 1]; // 等于上面的结果
                } else if (pre_top < 0) { // 这一排有 1，上面全是 0
                    f[i + 1][j + 1] = right - left + 1;
                    border[j] = {i, left, right};
                } else { // 这一排有 1，上面也有 1
                    int l = min(pre_left, left), r = max(pre_right, right);
                    f[i + 1][j + 1] = (r - l + 1) * (i - pre_top + 1);
                    border[j] = {pre_top, l, r};
                }
            }
        }
        return f;
    }

    int f(vector<vector<int>>& a) {
        int m = a.size(), n = a[0].size();
        vector<pair<int, int>> lr(m); // 每一行最左最右 1 的列号
        for (int i = 0; i < m; i++) {
            int l = -1, r = 0;
            for (int j = 0; j < n; j++) {
                if (a[i][j] > 0) {
                    if (l < 0) {
                        l = j;
                    }
                    r = j;
                }
            }
            lr[i] = {l, r};
        }

        // lt[i+1][j+1] = 包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        vector<vector<int>> lt = minimumArea(a);
        a = rotate(a);
        // lb[i][j+1] = 包含【左下角为 (m-1,0) 右上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        vector<vector<int>> lb = rotate(rotate(rotate(minimumArea(a))));
        a = rotate(a);
        // rb[i][j] = 包含【右下角为 (m-1,n-1) 左上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        vector<vector<int>> rb = rotate(rotate(minimumArea(a)));
        a = rotate(a);
        // rt[i+1][j] = 包含【右上角为 (0,n-1) 左下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        vector<vector<int>> rt = rotate(minimumArea(a));

        int ans = INT_MAX;
        if (m >= 3) {
            for (int i = 1; i < m; i++) {
                int left = n, right = 0, top = m, bottom = 0;
                for (int j = i + 1; j < m; j++) {
                    if (auto& [l, r] = lr[j - 1]; l >= 0) {
                        left = min(left, l);
                        right = max(right, r);
                        top = min(top, j - 1);
                        bottom = j - 1;
                    }
                    // 图片上左
                    ans = min(ans, lt[i][n] + (right - left + 1) * (bottom - top + 1) + lb[j][n]);
                }
            }
        }

        if (m >= 2 && n >= 2) {
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    // 图片上中
                    ans = min(ans, lt[i][n] + lb[i][j] + rb[i][j]);
                    // 图片上右
                    ans = min(ans, lt[i][j] + rt[i][j] + lb[i][n]);
                }
            }
        }
        return ans;
    }

public:
    int minimumSum(vector<vector<int>>& grid) {
        auto g = rotate(grid);
        return min(f(grid), f(g));
    }
};

java 解法, 执行用时: 11 ms, 内存消耗: 44 MB, 提交时间: 2024-06-28 17:52:29

class Solution {
    public int minimumSum(int[][] grid) {
        return Math.min(f(grid), f(rotate(grid)));
    }

    private int f(int[][] a) {
        int m = a.length;
        int n = a[0].length;
        int[][] lr = new int[m][2]; // 每一行最左最右 1 的列号
        for (int i = 0; i < m; i++) {
            int l = -1;
            int r = 0;
            for (int j = 0; j < n; j++) {
                if (a[i][j] > 0) {
                    if (l < 0) {
                        l = j;
                    }
                    r = j;
                }
            }
            lr[i][0] = l;
            lr[i][1] = r;
        }

        // lt[i+1][j+1] = 包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        int[][] lt = minimumArea(a);
        a = rotate(a);
        // lb[i][j+1] = 包含【左下角为 (m-1,0) 右上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        int[][] lb = rotate(rotate(rotate(minimumArea(a))));
        a = rotate(a);
        // rb[i][j] = 包含【右下角为 (m-1,n-1) 左上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        int[][] rb = rotate(rotate(minimumArea(a)));
        a = rotate(a);
        // rt[i+1][j] = 包含【右上角为 (0,n-1) 左下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        int[][] rt = rotate(minimumArea(a));

        int ans = Integer.MAX_VALUE;
        if (m >= 3) {
            for (int i = 1; i < m; i++) {
                int left = n;
                int right = 0;
                int top = m;
                int bottom = 0;
                for (int j = i + 1; j < m; j++) {
                    int l = lr[j - 1][0];
                    if (l >= 0) {
                        left = Math.min(left, l);
                        right = Math.max(right, lr[j - 1][1]);
                        top = Math.min(top, j - 1);
                        bottom = j - 1;
                    }
                    // 图片上左
                    ans = Math.min(ans, lt[i][n] + (right - left + 1) * (bottom - top + 1) + lb[j][n]);
                }
            }
        }

        if (m >= 2 && n >= 2) {
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    // 图片上中
                    ans = Math.min(ans, lt[i][n] + lb[i][j] + rb[i][j]);
                    // 图片上右
                    ans = Math.min(ans, lt[i][j] + rt[i][j] + lb[i][n]);
                }
            }
        }
        return ans;
    }

    private int[][] minimumArea(int[][] a) {
        int m = a.length;
        int n = a[0].length;
        // f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        int[][] f = new int[m + 1][n + 1];
        int[][] border = new int[n][3];
        for (int j = 0; j < n; j++) {
            border[j][0] = -1;
        }
        for (int i = 0; i < m; i++) {
            int left = -1;
            int right = 0;
            for (int j = 0; j < n; j++) {
                if (a[i][j] == 1) {
                    if (left < 0) {
                        left = j;
                    }
                    right = j;
                }
                int[] preB = border[j];
                if (left < 0) { // 这一排目前全是 0
                    f[i + 1][j + 1] = f[i][j + 1]; // 等于上面的结果
                } else if (preB[0] < 0) { // 这一排有 1，上面全是 0
                    f[i + 1][j + 1] = right - left + 1;
                    border[j][0] = i;
                    border[j][1] = left;
                    border[j][2] = right;
                } else { // 这一排有 1，上面也有 1
                    int l = Math.min(preB[1], left);
                    int r = Math.max(preB[2], right);
                    f[i + 1][j + 1] = (r - l + 1) * (i - preB[0] + 1);
                    border[j][1] = l;
                    border[j][2] = r;
                }
            }
        }
        return f;
    }

    // 顺时针旋转矩阵 90°
    private int[][] rotate(int[][] a) {
        int m = a.length;
        int n = a[0].length;
        int[][] b = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                b[j][m - 1 - i] = a[i][j];
            }
        }
        return b;
    }
}

golang 解法, 执行用时: 17 ms, 内存消耗: 7 MB, 提交时间: 2024-06-28 17:52:13

func minimumArea(a [][]int) [][]int {
    m, n := len(a), len(a[0])
    // f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    type data struct{ top, left, right int }
    border := make([]data, n)
    for j := range border {
        border[j].top = -1 // 无
    }

    for i, row := range a {
        left, right := -1, 0
        for j, x := range row {
            if x > 0 {
                if left < 0 {
                    left = j
                }
                right = j
            }
            preB := border[j]
            if left < 0 { // 这一排目前全是 0
                f[i+1][j+1] = f[i][j+1] // 等于上面的结果
            } else if preB.top < 0 { // 这一排有 1，上面全是 0
                f[i+1][j+1] = right - left + 1
                border[j] = data{i, left, right}
            } else { // 这一排有 1，上面也有 1
                l, r := min(preB.left, left), max(preB.right, right)
                f[i+1][j+1] = (r - l + 1) * (i - preB.top + 1)
                border[j] = data{preB.top, l, r}
            }
        }
    }
    return f
}

func minimumSum(grid [][]int) int {
    ans := math.MaxInt
    f := func(a [][]int) {
        m, n := len(a), len(a[0])
        type pair struct{ l, r int }
        lr := make([]pair, m) // 每一行最左最右 1 的列号
        for i, row := range a {
            l, r := -1, 0
            for j, x := range row {
                if x > 0 {
                    if l < 0 {
                        l = j
                    }
                    r = j
                }
            }
            lr[i] = pair{l, r}
        }

        // lt[i+1][j+1] = 包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        lt := minimumArea(a)
        a = rotate(a)
        // lb[i][j+1] = 包含【左下角为 (m-1,0) 右上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        lb := rotate(rotate(rotate(minimumArea(a))))
        a = rotate(a)
        // rb[i][j] = 包含【右下角为 (m-1,n-1) 左上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        rb := rotate(rotate(minimumArea(a)))
        a = rotate(a)
        // rt[i+1][j] = 包含【右上角为 (0,n-1) 左下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        rt := rotate(minimumArea(a))

        if m >= 3 {
            for i := 1; i < m; i++ {
                left, right, top, bottom := n, 0, m, 0
                for j := i + 1; j < m; j++ {
                    if p := lr[j-1]; p.l >= 0 {
                        left = min(left, p.l)
                        right = max(right, p.r)
                        top = min(top, j-1)
                        bottom = j - 1
                    }
                    // 图片上左
                    area := lt[i][n] // minimumArea(a[:i], 0, n)
                    area += (right - left + 1) * (bottom - top + 1) // minimumArea(a[i:j], 0, n)
                    area += lb[j][n] // minimumArea(a[j:], 0, n)
                    ans = min(ans, area)
                }
            }
        }

        if m >= 2 && n >= 2 {
            for i := 1; i < m; i++ {
                for j := 1; j < n; j++ {
                    // 图片上中
                    area := lt[i][n] // minimumArea(a[:i], 0, n)
                    area += lb[i][j] // minimumArea(a[i:], 0, j)
                    area += rb[i][j] // minimumArea(a[i:], j, n)
                    ans = min(ans, area)
                    // 图片上右
                    area = lt[i][j]  // minimumArea(a[:i], 0, j)
                    area += rt[i][j] // minimumArea(a[:i], j, n)
                    area += lb[i][n] // minimumArea(a[i:], 0, n)
                    ans = min(ans, area)
                }
            }
        }
    }
    f(grid)
    f(rotate(grid))
    return ans
}

// 顺时针旋转矩阵 90°
func rotate(a [][]int) [][]int {
    m, n := len(a), len(a[0])
    b := make([][]int, n)
    for i := range b {
        b[i] = make([]int, m)
    }
    for i, row := range a {
        for j, x := range row {
            b[j][m-1-i] = x
        }
    }
    return b
}

python3 解法, 执行用时: 135 ms, 内存消耗: 16.7 MB, 提交时间: 2024-06-28 17:51:50

# dp处理
class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        return min(self.f(grid), self.f(rotate(grid)))

    def f(self, a: List[List[int]]) -> int:
        m, n = len(a), len(a[0])
        lr = []  # 每一行最左最右 1 的列号
        for i in range(m):
            l, r = -1, 0
            for j in range(n):
                if a[i][j] > 0:
                    if l < 0:
                        l = j
                    r = j
            lr.append((l, r))

        def minimumArea(a: List[List[int]]) -> List[List[int]]:
            m, n = len(a), len(a[0])
            # f[i+1][j+1] 表示包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
            f = [[0] * (n + 1) for _ in range(m + 1)]
            border = [(-1, 0, 0)] * n
            for i, row in enumerate(a):
                left, right = -1, 0
                for j, x in enumerate(row):
                    if x:
                        if left < 0:
                            left = j
                        right = j
                    pre_top, pre_left, pre_right = border[j]
                    if left < 0:  # 这一排目前全是 0
                        f[i + 1][j + 1] = f[i][j + 1]  # 等于上面的结果
                    elif pre_top < 0:  # 这一排有 1，上面全是 0
                        f[i + 1][j + 1] = right - left + 1
                        border[j] = (i, left, right)
                    else:  # 这一排有 1，上面也有 1
                        l = min(pre_left, left)
                        r = max(pre_right, right)
                        f[i + 1][j + 1] = (r - l + 1) * (i - pre_top + 1)
                        border[j] = (pre_top, l, r)
            return f

        # lt[i+1][j+1] = 包含【左上角为 (0,0) 右下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        lt = minimumArea(a)
        a = rotate(a)
        # lb[i][j+1] = 包含【左下角为 (m-1,0) 右上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        lb = rotate(rotate(rotate(minimumArea(a))))
        a = rotate(a)
        # rb[i][j] = 包含【右下角为 (m-1,n-1) 左上角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        rb = rotate(rotate(minimumArea(a)))
        a = rotate(a)
        # rt[i+1][j] = 包含【右上角为 (0,n-1) 左下角为 (i,j) 的子矩形】中的所有 1 的最小矩形面积
        rt = rotate(minimumArea(a))

        ans = inf
        if m >= 3:
            for i in range(1, m):
                left, right, top, bottom = n, 0, m, 0
                for j in range(i + 1, m):
                    l, r = lr[j - 1]
                    if l >= 0:
                        left = min(left, l)
                        right = max(right, r)
                        top = min(top, j - 1)
                        bottom = j - 1
                    # 图片上左
                    ans = min(ans, lt[i][n] + (right - left + 1) * (bottom - top + 1) + lb[j][n])

        if m >= 2 and n >= 2:
            for i in range(1, m):
                for j in range(1, n):
                    # 图片上中
                    ans = min(ans, lt[i][n] + lb[i][j] + rb[i][j])
                    # 图片上右
                    ans = min(ans, lt[i][j] + rt[i][j] + lb[i][n])
        return ans

# 顺时针旋转矩阵 90°
def rotate(a: List[List[int]]) -> List[List[int]]:
    return list(zip(*reversed(a)))

golang 解法, 执行用时: 96 ms, 内存消耗: 3.8 MB, 提交时间: 2024-06-28 17:51:10

func minimumArea(a [][]int, l, r int) int {
    left, right := len(a[0]), 0
    top, bottom := len(a), 0
    for i, row := range a {
        for j, x := range row[l:r] {
            if x == 1 {
                left = min(left, j)
                right = max(right, j)
                top = min(top, i)
                bottom = i
            }
        }
    }
    return (right - left + 1) * (bottom - top + 1)
}

func minimumSum(grid [][]int) int {
    ans := math.MaxInt
    f := func(a [][]int) {
        m, n := len(a), len(a[0])
        if m >= 3 {
            for i := 1; i < m; i++ {
                for j := i + 1; j < m; j++ {
                    // 图片上左
                    area := minimumArea(a[:i], 0, n)
                    area += minimumArea(a[i:j], 0, n)
                    area += minimumArea(a[j:], 0, n)
                    ans = min(ans, area)
                }
            }
        }
        if m >= 2 && n >= 2 {
            for i := 1; i < m; i++ {
                for j := 1; j < n; j++ {
                    // 图片上中
                    area := minimumArea(a[:i], 0, n)
                    area += minimumArea(a[i:], 0, j)
                    area += minimumArea(a[i:], j, n)
                    ans = min(ans, area)
                    // 图片上右
                    area = minimumArea(a[:i], 0, j)
                    area += minimumArea(a[:i], j, n)
                    area += minimumArea(a[i:], 0, n)
                    ans = min(ans, area)
                }
            }
        }
    }
    f(grid)
    f(rotate(grid))
    return ans
}

// 顺时针旋转矩阵 90°
func rotate(a [][]int) [][]int {
    m, n := len(a), len(a[0])
    b := make([][]int, n)
    for i := range b {
        b[i] = make([]int, m)
    }
    for i, row := range a {
        for j, x := range row {
            b[j][m-1-i] = x
        }
    }
    return b
}

python3 解法, 执行用时: 5901 ms, 内存消耗: 16.8 MB, 提交时间: 2024-06-28 17:50:53

# 六种情况，暴力枚举
class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        return min(self.f(grid), self.f(self.rotate(grid)))

    def f(self, a: List[List[int]]) -> int:
        def minimumArea(a: List[List[int]], l: int, r: int) -> int:
            left, right = len(a[0]), 0
            top, bottom = len(a), 0
            for i, row in enumerate(a):
                for j, x in enumerate(row[l:r]):
                    if x == 1:
                        left = min(left, j)
                        right = max(right, j)
                        top = min(top, i)
                        bottom = i
            return (right - left + 1) * (bottom - top + 1)

        ans = inf
        m, n = len(a), len(a[0])
        if m >= 3:
            for i in range(1, m):
                for j in range(i + 1, m):
                    # 图片上左
                    area = minimumArea(a[:i], 0, n)
                    area += minimumArea(a[i:j], 0, n)
                    area += minimumArea(a[j:], 0, n)
                    ans = min(ans, area)
        if m >= 2 and n >= 2:
            for i in range(1, m):
                for j in range(1, n):
                    # 图片上中
                    area = minimumArea(a[:i], 0, n)
                    area += minimumArea(a[i:], 0, j)
                    area += minimumArea(a[i:], j, n)
                    ans = min(ans, area)
                    # 图片上右
                    area = minimumArea(a[:i], 0, j)
                    area += minimumArea(a[:i], j, n)
                    area += minimumArea(a[i:], 0, n)
                    ans = min(ans, area)
        return ans

    # 顺时针旋转矩阵 90°
    def rotate(self, a: List[List[int]]) -> List[List[int]]:
        return list(zip(*reversed(a)))