Как переместить ладью в правый нижний угол квадрата 15x15 так, чтобы сумма чисел в клетках, через которые она проходит

Тема: Перемещение ладьи в правый нижний угол квадрата 15x15 с максимальной суммой чисел

Описание: Для решения данной задачи, нам необходимо определить оптимальный маршрут перемещения ладьи в правый нижний угол квадрата 15x15 с максимальной суммой чисел. Ладья может перемещаться только по горизонтали и вертикали, т.е. она может двигаться только вправо или вниз.

Рассмотрим следующий алгоритм:

1. Создадим квадрат 15x15 и заполним его числами. Каждая клетка будет содержать случайное число (можно задать свои ограничения для получения интересных результатов).

2. Найдем максимальную сумму чисел при движении только вправо или только вниз. Для этого заполним две дополнительные матрицы 15x15. В первой матрице будем хранить сумму чисел от левого верхнего угла до текущей клетки при движении только вправо. Во второй матрице будем хранить сумму чисел от левого верхнего угла до текущей клетки при движении только вниз.

3. Для каждой клетки квадрата 15x15, вычислим максимальную сумму чисел, если ладья переместится в эту клетку из клетки сверху или слева. Для этого выберем максимум из суммы чисел в верхней клетке и суммы чисел в левой клетке и добавим значение числа в текущей клетке.

4. Продолжим вычисление максимальной суммы чисел для каждой клетки до правого нижнего угла.

5. Максимальная сумма чисел, полученная для правого нижнего угла, будет ответом на задачу.

Пример использования:
Предположим, у нас есть следующая матрица 15x15:

1 2 3 4 ... 14 15
1 2 3 4 ... 14 15
...
1 2 3 4 ... 14 15
1 2 3 4 ... 14 15

Максимальная сумма чисел при перемещении ладьи в правый нижний угол будет определена алгоритмом, описанным выше.

Совет: Чтобы лучше понять алгоритм, можно нарисовать небольшой пример матрицы, заполнить ее случайными числами и последовательно провести вычисления по описанному алгоритму. Это поможет лучше понять логику решения задачи.

Практическое задание:
Предположим, у нас следующая матрица 4x4:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Чему будет равна максимальная сумма чисел при перемещении ладьи в правый нижний угол?