1. Введение

В задании №18 нужно провести Робота по клетчатому полю и определить наибольшую или наименьшую сумму значений на допустимом маршруте.

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

Каждая клетка хранит число. Когда Робот посещает клетку, это число прибавляется к накопленной сумме.

Поэтому для каждой доступной клетки удобно записать лучший результат, с которым Робот может в неё прийти.

Главная идея

Значение в новой таблице — это число из текущей клетки плюс лучший результат из клетки, откуда Робот мог прийти.

Для максимальной суммы выбираем МАКС, для минимальной — МИН.

2. Шаги выполнения

1. Читаем условие

Сначала отмечаем:

  • направление движения;
  • стартовую клетку;
  • возможные конечные клетки;
  • положение стен;
  • что требуется найти: максимум, минимум или оба значения.

На примере из файла Робот идёт вправо и вниз, а жёлтым показаны три допустимых конца маршрута.

1

2. Создаём таблицу для накопленных сумм

Копируем исходное поле и вставляем копию под ним.

Верхняя таблица остаётся источником значений клеток, а в нижней будем считать суммы.

Так исходные числа и стены всегда остаются перед глазами.

1

3. Заполняем старт и крайние клетки

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

В клетку первой строки можно прийти только слева, а в клетку первого столбца — только сверху.

Поэтому здесь не нужно выбирать между двумя маршрутами: прибавляем значение текущей клетки к уже посчитанной соседней.

Для первой строки:

= значение текущей клетки + накопленная сумма слева

Формулу растягиваем вправо до конца поля.

Для первого столбца:

= значение текущей клетки + накопленная сумма сверху

Формулу растягиваем вниз до конца поля.

1

4. Считаем внутренние клетки

Во внутреннюю клетку без стены Робот может попасть:

  • сверху;
  • слева.

Для максимального пути прибавляем больший из двух накопленных результатов:

= текущая_клетка + МАКС(слева; сверху)

Для минимального пути прибавляем меньший:

= текущая_клетка + МИН(слева; сверху)

Формулу с МАКС или МИН растягиваем на всю оставшуюся часть расчётной таблицы.

1

5. Возвращаем стенки

После копирования формул границы стен могут исчезнуть.

Выделяем исходную таблицу и нажимаем на кисточку «Клонирование форматирования».

В LibreOffice Calc она находится слева сверху на панели инструментов.

Затем нажимаем на первую клетку расчётной таблицы.

Числа и формулы не меняются — возвращается только оформление стен.

1

6. Исправляем формулы около стен

Стена запрещает переход.

Если стена находится сверху, в формуле оставляем только путь слева:

стена сверху → текущая клетка + результат слева

То есть убираем вариант прихода сверху.

Если стена находится слева, оставляем только путь сверху:

стена слева → текущая клетка + результат сверху

То есть убираем вариант прихода слева.

Исправленную формулу растягиваем вдоль всей стенки.

1

7. Берём ответ в нужной конечной клетке

Если конечная клетка одна, записываем значение только из неё.

Если условие считает концами несколько угловых клеток, выписываем результаты из всех таких клеток и выбираем требуемый максимум или минимум.

Чтобы получить второй вариант расчёта, можно заменить во всех формулах:

МАКС

на:

МИН

через функцию «Найти и заменить».

1

3. На чём могут подловить

Берём только те концы, которые названы в условии

Если сказано:

«из правой верхней клетки в левую нижнюю»

ответ берём только из левой нижней клетки.

Другие углы стенок в этом случае не являются ответами.

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

Недоступные области нужно исключить

Иногда стены полностью отрезают часть таблицы: Робот не может попасть внутрь этой области ни одним разрешённым ходом.

Формулы и значения внутри неё нужно удалить.

Можно поставить нули, но только если формулы устроены так, что эти нули не будут ошибочно выбраны функцией МИН или МАКС.

Быстрая проверка перед ответом

Проследи путь от каждой клетки с ответом назад к старту.

Если хотя бы на одном участке пришлось бы:

  • пройти сквозь стену;
  • войти в полностью закрытую область,

результат этой клетки использовать нельзя.

1