Three Rooks on a Big Board

Hard

The cells of a rectangular board grid (m rows, n columns) are labeled with integers, their values, which may be negative. Place three rooks so that no two of them share a row or a column (so none attacks another), and return the maximum total value of the occupied cells. The board can be as large as 500 × 500, so trying every triple of cells will not fit in the time limit.

Example 1

grid=[[1, 8, 3, 2], [7, 9, 0, 1], [4, 6, 5, 2]] → 20

The most valuable cell, 9, blocks both the 8 and the 7. Taking 8 + 7 + 5 = 20 on (0, 1), (1, 0), (2, 2) is better.

Example 2

grid=[[3, 3, 3], [3, 3, 3], [3, 3, 3]] → 9

Any placement with no shared row or column works: 3 + 3 + 3 = 9.

Example 3

grid=[[0, -4, 10], [-4, 0, 10], [10, -4, 0]] → 20

Constraints

3 ≤ m = len(grid) ≤ 500
3 ≤ n = len(grid[i]) ≤ 500
-10⁹ ≤ grid[i][j] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Enumeration Matrix

Similar problems

Three Peaceful Rooks Hard Biggest Solid Panel Block Hard Crossing the Cave Hard Longest Uphill Walk Hard Weeks of Rest by Flight Hard

Input

grid=[[1, 8, 3, 2], [7, 9, 0, 1], [4, 6, 5, 2]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 84 tests on the server, hidden ones included.