Задача к ЕГЭ по информатике на тему «шахматные фигуры» №2

Квадрат разлинован на $N × N$ клеток. В левом верхнем углу квадрата стоит ладья. Ладья может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо X или вниз X. По команде вправо ладья перемещается на X клеток вправо, по команде вниз – на X клеток вниз, где $1 ≤ X ≤ N$ . Квадрат ограничен внешними стенами, стены также могут быть внутри квадрата, сквозь стену ладья пройти не может. Перед стартом ладьи в каждой клетке квадрата записывается число от 1 до 100.

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

Исходные данные представляют собой электронную таблицу размером $N × N$ , каждая ячейка которой соответствует клетке квадрата.

Нам дано поле 16 на 16, создадим еще одно поле такого же размера ниже (ячейки $A20 : P 35$ ).

Сначала решим задачу как будто в ней нет стен. В стартовой ячейке $A20$ запишем значение из соответствующей ячейки $A1$ . В остальные ячейки первой строки ладья может попасть из любой ячейки левее, а в остальные ячейки первого столбца ладья может попасть из любой ячейки выше.

Для ячейки $B20$ напишем следующу формулу:

=МИН($A20:A20)+B1

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

Аналогично напишем формулу для ячейки $A21$ для первого столбца, но для растяжения формулы вниз уже закрепим номер строки стартовой ячейки:

=МИН(A$20:A20)+A2

Теперь напишем формулу для ячейки $B21$ , которая является внутренней ячейкой поля. В неё ладья может попасть из любой ячейки выше или левее. Значит нужно в формуле выделить два диапазона: от самой левой ячейки до последней в строке перед ячейкой и от самой верхней ячейки до последней в столбце перед ячейкой.

Тогда напишем формулу для ячейки $B21$ , закрепив для растяжения по строкам столбец первой ячейки строки и закрепив для растяжения по столбцам номер первой ячейки столбца:

=МИН($A21:A21;B$20:B20)+B2

Растянем эту формулу по всему полю. Теперь, чтобы учесть стены, скопируем исходную таблицу и перенесём форматирование с помощью специальной вставки. После этого нужно изменить формулы в ячейках, которые находятся справа от стены или ниже стены. Ладья в таком случае не сможет прийти из ячеек в столбце, которые будут выше стены, или из ячеек в строке, которые будут левее стены.

Для ячеек, которые находятся вплотную к стене, нужно удалить диапазон, откуда ладья не может попасть. Например для ячейки $B27$ будет следующая формула:

=МИН($A27:A27)+B8

А ячейки, которые находятся ниже ячейки, стоящей к стене вплотную, нужно поменять начальный столбец и/или строку. Например для ячейки $J25$ будет следующая формула:

=МИН($E25:I25;J$23:J24)+J6

Получим следующую таблицу (ячейки, формулы которых требовалось изменить, выделены соответствующими цветами):

Теперь, когда все формулы скорректированы с учётом стен, в ячейке $P35$ находится минимальная сумма, которую можно брать в ответ.

Для того, чтобы найти максимальную сумму необходимо заменить во всех формулах МИН на МАКС.

Ответ: 2170 87