<p>You are given a <code>m x n</code> 2D array <code>board</code> representing a chessboard, where <code>board[i][j]</code> represents the <strong>value</strong> of the cell <code>(i, j)</code>.</p>

<p>Rooks in the <strong>same</strong> row or column <strong>attack</strong> each other. You need to place <em>three</em> rooks on the chessboard such that the rooks <strong>do not</strong> <strong>attack</strong> each other.</p>

<p>Return the <strong>maximum</strong> sum of the cell <strong>values</strong> on which the rooks are placed.</p>

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

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

<p><strong>Output:</strong> 4</p>

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

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/08/rooks2.png" style="width: 294px; height: 450px;" /></p>

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 3)</code>, and <code>(2, 1)</code> for a sum of <code>1 + 1 + 2 = 4</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,2,3],[4,5,6],[7,8,9]]</span></p>

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

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

<p>We can place the rooks in the cells <code>(0, 0)</code>, <code>(1, 1)</code>, and <code>(2, 2)</code> for a sum of <code>1 + 5 + 9 = 15</code>.</p>
</div>

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

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

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

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

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 1)</code>, and <code>(2, 0)</code> for a sum of <code>1 + 1 + 1 = 3</code>.</p>
</div>

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

<ul>
	<li><code>3 &lt;= m == board.length &lt;= 100</code></li>
	<li><code>3 &lt;= n == board[i].length &lt;= 100</code></li>
	<li><code>-10<sup>9</sup> &lt;= board[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        # go through every cell, and sort them from largest score to smallest
        # in a flat list
        allVals = []
        for y, row in enumerate(board):
            for x, cell in enumerate(row):
                allVals.append((cell, y, x))
        allVals.sort(reverse=True)
        # we don't care about any of the small values in each row after 3
        # source: a leetcode content comment by l1cache__
        newVals = []
        yCounts = defaultdict(int)
        for val in allVals:
            cell, y, x = val
            if yCounts[y] >= 3:
                continue
            yCounts[y] += 1
            newVals.append(val)
        allVals = newVals
        # now we can easily visit them in order from largest to smallest cells
        # and simulate the world where we started from here, keeping track of the offlimit
        # rows and stuff until we hit 3 placed, and using a min heap to keep our score good
        worlds = [] # cur score inverted, next pos, used count, used rows, used cols
        for x, val in enumerate(allVals):
            rScore, rRow, rCol = val
            heappush(worlds, (-1*rScore, x+1, 1, set([rRow]), set([rCol])))
        bestScore = None
        while worlds:
            score, pos, count, usedRows, usedCols = heappop(worlds)
            # print(score, pos, count, usedRows, usedCols)
            score *= -1
            if count >= 3:
                # we're finished?!
                if bestScore == None:
                    bestScore = score
                else:
                    bestScore = max(bestScore, score)
                continue
            if pos >= len(allVals):
                # out of bounds (shouldn't happen?)
                continue
            for x in range(pos, len(allVals)):
                # all following worlds from here (memory intensive search)
                rScore, rRow, rCol = allVals[x]
                # only append if we have a shot at beating the best score
                if count == 2 and bestScore != None and rScore + score <= bestScore:
                    continue
                # the world where we take the rook at this pos (if we can)
                if rRow not in usedRows and rCol not in usedCols:
                    newRows = usedRows.copy()
                    newRows.add(rRow)
                    newCols = usedCols.copy()
                    newCols.add(rCol)
                    heappush(worlds, (-1*(score + rScore), pos+1, (count+1), newRows, newCols))
        return bestScore
98288