aboutsummaryrefslogtreecommitdiff
path: root/find_min_area_conver_ones2.py
blob: c61d18d136784a982d550e28124dbbd8fd591c66 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 3197. Find the Minimum Area to Cover All Ones II

"""
you are giiven 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 the 'grid' lie inside these rectangles. return the minimum
possible sum of the area of these rectangles. note that the rectangles are
allowed to touch.
"""


class Solution(object):
    def min_area(self, grid):
        if not grid or not grid[0]:
            return 0
        n, m = len(grid), len(grid[0])
        left, top, right, bottom = float("inf"), float("inf"), -1, -1
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    left = min(left, j)
                    top = min(top, i)
                    right = max(right, j)
                    bottom = max(bottom, i)
        if right == -1:
            return 0
        return (right - left + 1) * (bottom - top + 1)

    def rotate(self, grid):
        n, m = len(grid), len(grid[0])
        return [[grid[i][j] for i in range(n - 1, -1, -1)] for j in range(m)]

    def minimumSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        ans = float("inf")
        for _ in range(4):
            n, m = len(grid), len(grid[0])
            for i in range(1, n):
                a1 = self.min_area(grid[:i])
                for j in range(1, m):
                    p2 = [row[:j] for row in grid[i:]]
                    p3 = [row[j:] for row in grid[i:]]
                    a2 = self.min_area(p2)
                    a3 = self.min_area(p3)
                    ans = min(ans, a1 + a2 + a3)
                for i2 in range(i + 1, n):
                    p2 = grid[i:i2]
                    p3 = grid[i2:]
                    a2 = self.min_area(p2)
                    a3 = self.min_area(p3)
                    ans = min(ans, a1 + a2 + a3)
            grid = self.rotate(grid)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.minimumSum(grid=[[1, 0, 1], [1, 1, 1]]))
    print(obj.minimumSum(grid=[[1, 0, 1, 0], [0, 1, 0, 1]]))