3256. Maximum Value Sum by Placing Three Rooks I
Description
You are given a m x n 2D array board representing a chessboard, where board[i][j] represents the value of the cell (i, j).
Rooks in the same row or column attack each other. You need to place three rooks on the chessboard such that the rooks do not attack each other.
Return the maximum sum of the cell values on which the rooks are placed.
Example 1:
Input: board = [[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
Output: 4
Explanation:
We can place the rooks in the cells (0, 2), (1, 3), and (2, 1) for a sum of 1 + 1 + 2 = 4.
Example 2:
Input: board = [[1,2,3],[4,5,6],[7,8,9]]
Output: 15
Explanation:
We can place the rooks in the cells (0, 0), (1, 1), and (2, 2) for a sum of 1 + 5 + 9 = 15.
Example 3:
Input: board = [[1,1,1],[1,1,1],[1,1,1]]
Output: 3
Explanation:
We can place the rooks in the cells (0, 2), (1, 1), and (2, 0) for a sum of 1 + 1 + 1 = 3.
Constraints:
3 <= m == board.length <= 1003 <= n == board[i].length <= 100-109 <= board[i][j] <= 109
Solutions
Solution 1
Thinking
Place three rooks on distinct rows and columns to maximize the sum of cell values. \(m,n\le 100\), so trying every triple of cells is \(O((mn)^3)\). Each row only needs a few largest candidates, then we enumerate row triples and skip column clashes.
Keep the top cells of every row and try three rows with those columns. There is no implementation in the tree yet; the reasoning follows this “top-per-row, then enumerate rows” outline.
1 | |
1 | |
1 | |
1 | |