grid (m строк, n столбцов) подписаны целыми числами — это их ценность, она может быть и отрицательной.
Расставьте три ладьи так, чтобы никакие две не оказались в одной строке или в одном столбце (то есть они не бьют друг друга), и верните максимальную сумму ценностей занятых клеток.
Доска бывает до 500 × 500, поэтому перебор всех троек клеток не уложится во время.grid=[[1, 8, 3, 2], [7, 9, 0, 1], [4, 6, 5, 2]] → 20
Самая дорогая клетка 9 мешает восьмёрке и семёрке. Лучше взять 8 + 7 + 5 = 20: клетки (0, 1), (1, 0), (2, 2).
grid=[[3, 3, 3], [3, 3, 3], [3, 3, 3]] → 9
Подойдёт любая расстановка без общих строк и столбцов: 3 + 3 + 3 = 9.
grid=[[0, -4, 10], [-4, 0, 10], [10, -4, 0]] → 20
grid=[[1, 8, 3, 2], [7, 9, 0, 1], [4, 6, 5, 2]]
20
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 84 теста на сервере, включая скрытые.