Ладья

📌 Задание:

Дан квадрат. В левом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток вправо или вниз. Необходимо переместить ладью в правый нижний угол так, чтобы сумма чисел в клетках, в которых ладья останавливалась (включая начальную и конечную), была максимальной.

🎠 Итак, из задания мы получаем информацию, что ладья — это фигура, которая может ходить только вправо и вниз, причем перемещается на любое количество клеток.

🔍 Рассмотрим пример (смотри на картинку): ладья ходит из левого верхнего угла в правый нижний. В каждой клетке у нас стоит выбор из какой клетки горизонтального или вертикального ряда сходить. Так как в результате должны получить максимальное значение, тогда берем максимум из горизонтали и вертикали и складываем с текущим значение клетки.

Применим аналогию из примера на решение подзадачи: Начинаем ходить из ячейки Q1, в ячейках Q2:Qn — вставим формулу: =МАКС($Q$1:Q2)+A3 — фиксируем начало вертикального столбца, аналогично делаем с горизонтальной строкой: =МАКС($Q$1:R1)+C1. Для любой внутренней ячейке необходимо взять максимум из строки и столбца сверху и слева, например для S3: =МАКС($Q3:R3;S$1:S2)+C3.

💡Теперь если скопируем формулы для всего диапазона получим ответ!
(смотри файл с решением)