<p>You are given a 2D <strong>binary</strong> array <code>grid</code>. You need to find 3 <strong>non-overlapping</strong> rectangles having <strong>non-zero</strong> areas with horizontal and vertical sides such that all the 1&#39;s in <code>grid</code> lie inside these rectangles.</p>

<p>Return the <strong>minimum</strong> possible sum of the area of these rectangles.</p>

<p><strong>Note</strong> that the rectangles are allowed to touch.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1],[1,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example0rect21.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 280px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(1, 0)</code> are covered by a rectangle of area 2.</li>
	<li>The 1&#39;s at <code>(0, 2)</code> and <code>(1, 2)</code> are covered by a rectangle of area 2.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1,0],[0,1,0,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example1rect2.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 356px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(0, 2)</code> are covered by a rectangle of area 3.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
	<li>The 1 at <code>(1, 3)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either 0 or 1.</li>
	<li>The input is generated such that there are at least three 1&#39;s in <code>grid</code>.</li>
</ul>

class Solution:
    @cache
    def minimumArea(self, lur, luc, rbr, rbc) -> int:
        '''
        to ensure all 1s are covered
        rectangle would be defined by minR, maxR; minC, maxC
        https://leetcode.com/problems/find-the-minimum-area-to-cover-all-ones-i/
        0,2,0,3
        minR = 0
        maxR = 0
        minC = 3
        maxC = 2
        '''
        minR, maxR, minC, maxC = rbr,lur,rbc,luc
        for i in range(lur, rbr+1): #(0,0+1)
            for j in range(luc, rbc+1): #(2,3+1)
                if self.grid[i][j]==1:
                    minR = min(minR, i)
                    maxR = max(maxR, i)
                    minC = min(minC, j)
                    maxC = max(maxC, j)
        if (maxR-minR+1)*(maxC-minC+1)<=0:
            return math.inf
        return (maxR-minR+1)*(maxC-minC+1)
    
    def cutRectangleRecursive(self, lur, luc, rbr, rbc, numCuts):
        '''
        lu -> left upper; rb -> right bottom 
        lu => r,c
        '''
        #print(f"cutRectangle call: lur={lur},luc={luc},rbr={rbr},rbc={rbc}")
        if numCuts>=2:
            #
            #print(lur, luc, rbr, rbc, self.minimumArea(lur, luc, rbr, rbc))
            return self.minimumArea(lur, luc, rbr, rbc)
        # cut could be vertical or horizontal
        ## vertical cut (determined based on r)
        curSum = math.inf
        for v in range(luc,rbc):
            ## (lur,v), (rbr, )
            ## note (lur, luc), (rbr, luc) -> has breadth = 1
            ## rect1: (lur, luc), (rbr, v); rect2: (lur,v+1), (rbr,rbc)
            #print(f"vertical cut at v={v} => rect1: lur={lur},luc={luc},rbr={rbr},rbc={v}; rect2: lur={lur},luc={v+1},rbr={rbr},v={rbc};")
            #self.memo[(lur, luc, rbr, v)] = self.minimumArea(lur, luc, rbr, v)
            #self.memo[(lur, v+1, rbr, rbc)] = self.minimumArea(lur, v+1, rbr, rbc)
            curSum = min(curSum,
                        self.minimumArea(lur, luc, rbr, v) + self.cutRectangleRecursive(lur, v+1, rbr, rbc, numCuts+1),
                        self.minimumArea(lur, v+1, rbr, rbc) + self.cutRectangleRecursive(lur, luc, rbr, v, numCuts+1))


        for h in range(lur, rbr):
            ## (lur,luc), (h,rbc); (h+1,luc), (rbr, rbc)
            #print(f"horizontal cut at h={h} => rect1: lur={lur},luc={luc},rbr={h},rbc={rbc}; rect2: lur={h+1},luc={luc},rbr={rbr},v={rbc};")
            #self.memo[(lur, luc, h, rbc)] = self.minimumArea(lur, luc, h, rbc)
            #self.memo[(h+1, luc, rbr, rbc)] = self.minimumArea(h+1, luc, rbr, rbc)
            curSum = min(curSum,
                        self.minimumArea(lur, luc, h, rbc) + self.cutRectangleRecursive(h+1, luc, rbr, rbc, numCuts+1),
                        self.minimumArea(h+1, luc, rbr, rbc) + self.cutRectangleRecursive(lur, luc, h, rbc, numCuts+1))
        return curSum
    def cutRectangleBackTrack(self, lur, luc, rbr, rbc, numCuts, curArea):
        '''
        lu -> left upper; rb -> right bottom 
        lu => r,c
        '''
        #print(f"cutRectangle call: lur={lur},luc={luc},rbr={rbr},rbc={rbc}")
        if numCuts>=2:
            #
            #print(lur, luc, rbr, rbc, self.minimumArea(lur, luc, rbr, rbc))
            
            self.ans = min(self.ans, curArea + self.minimumArea(lur, luc, rbr, rbc))
            return
        # cut could be vertical or horizontal
        ## vertical cut (determined based on r)
        curSum = math.inf
        for v in range(luc,rbc):
            ## (lur,v), (rbr, )
            ## note (lur, luc), (rbr, luc) -> has breadth = 1
            ## rect1: (lur, luc), (rbr, v); rect2: (lur,v+1), (rbr,rbc)
            #print(f"vertical cut at v={v} => rect1: lur={lur},luc={luc},rbr={rbr},rbc={v}; rect2: lur={lur},luc={v+1},rbr={rbr},v={rbc};")
            #self.memo[(lur, luc, rbr, v)] = self.minimumArea(lur, luc, rbr, v)
            #self.memo[(lur, v+1, rbr, rbc)] = self.minimumArea(lur, v+1, rbr, rbc)
            self.cutRectangleBackTrack(lur, v+1, rbr, rbc, numCuts+1, curArea + self.minimumArea(lur, luc, rbr, v))
            self.cutRectangleBackTrack(lur, luc, rbr, v, numCuts+1, curArea + self.minimumArea(lur, v+1, rbr, rbc))


        for h in range(lur, rbr):
            ## (lur,luc), (h,rbc); (h+1,luc), (rbr, rbc)
            #print(f"horizontal cut at h={h} => rect1: lur={lur},luc={luc},rbr={h},rbc={rbc}; rect2: lur={h+1},luc={luc},rbr={rbr},v={rbc};")
            #self.memo[(lur, luc, h, rbc)] = self.minimumArea(lur, luc, h, rbc)
            #self.memo[(h+1, luc, rbr, rbc)] = self.minimumArea(h+1, luc, rbr, rbc)
            self.cutRectangleBackTrack(h+1, luc, rbr, rbc, numCuts+1, curArea + self.minimumArea(lur, luc, h, rbc))
            self.cutRectangleBackTrack(lur, luc, h, rbc, numCuts+1, curArea + self.minimumArea(h+1, luc, rbr, rbc))
    
    def minimumSum(self, grid: List[List[int]]) -> int:
        '''
        approaches:
        from part 1: i can find the min.area that covers all 1s => ans for this min.area.ii<min.area.i
        I can create area by removing 0s from ths min.area.i
        I could have bruteforced, but I dont know how to decide after removing the zeros -> that 3 rectangles will be maintained
        
        => can I think of all 1s as connected component ? and connect these ?
        => can I think of all 0s as connected components and remove these ?
        
        '''
        self.grid = grid
        self.memo = {}
        self.ans = math.inf
        #self.cutRectangleBackTrack(0,0,len(grid)-1, len(grid[0])-1,0,0)
        
        #return self.ans
        return self.cutRectangleRecursive(0,0,len(grid)-1, len(grid[0])-1,0)
2076