Three Peaceful Rooks

Hard

You get an m × n board grid; every cell holds an integer, its value. Place three rooks on the board so that none of them attacks another: no two may share a row or a column. Return the largest possible sum of the values of the cells the rooks stand on.

Example 1

grid=[[2, -1, 5], [0, 4, 4], [6, 1, -2]] → 15

Rooks on (0, 2), (1, 1) and (2, 0): 5 + 4 + 6 = 15, with every row and column different.

Example 2

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

Every value is negative, yet all three rooks must be placed: the best choice is (0, 1), (1, 2), (2, 3) for a total of -3.

Example 3

grid=[[9, 9, 0], [9, 9, 0], [0, 0, 0]] → 18

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 Rooks on a Big Board Hard Biggest Solid Panel Block Hard Crossing the Cave Hard Longest Uphill Walk Hard Weeks of Rest by Flight Hard

Input

grid=[[2, -1, 5], [0, 4, 4], [6, 1, -2]]

Expected

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