Задание №18. Короткий конспект
Суммы до клетки, допустимые предшественники, стены, тупики и проверка порядка ответа.
Робот движется на одну клетку вправо или вниз. Накопленная сумма включает значения всех клеток пути от старта до текущей клетки. Минимум и максимум вычисляются отдельно; оба учитывают начальную и конечную клетки, если это предусмотрено условием.
Правило заполнения
Предшественник — клетка, из которой возможен последний шаг: сверху или слева. Она участвует в расчёте, только если достижима от старта и переход не закрыт стеной.
| Ситуация | Накопленная сумма |
|---|---|
| Начальная клетка | Её собственное значение |
| Один доступный предшественник | Его сумма плюс значение клетки |
| Два доступных предшественника | Меньшая или большая из их сумм плюс значение клетки |
| Нет предшественников, это не старт | Клетка недостижима; суммы нет |
Контроль по фрагменту поля без стен ↗: в B2 стоит 11, до B1 накоплено 43, до A2 — 50. Минимум 11+43=54, максимум 11+50=61.
Порядок решения
- По условию определяются старт, допустимые финиши, движения, учёт крайних клеток и порядок двух чисел ответа.
- Рабочий файл отделяется от рисунка-примера. Исходные значения и стены сохраняются; для минимальных и максимальных сумм создаются отдельные таблицы.
- В старт записывается его значение. Первые строка и столбец заполняются с учётом единственного направления и возможных стен.
- Остальные клетки обрабатываются по строкам сверху вниз, слева направо. Сравниваются уже накопленные суммы доступных предшественников.
- При заданном финише берутся результаты этой клетки. При движении до тупика сравниваются результаты всех достижимых клеток без разрешённых выходов вправо и вниз.
Возможные ловушки
- Сравнение исходных соседних чисел: теряется стоимость начала пути. В формулу подставляются суммы до соседей.
- Ноль за стеной: создаёт ложный путь для минимума. В поле со стенами ↗ запрещённый переход исключается, а доступ с другой стороны сохраняется.
- Один финиш по привычке: в условии о любом тупике ↗ минимум и максимум могут закончиться в разных клетках. Нужен весь набор допустимых финишей.
Проверка результата: восстановленный путь не пересекает стены, содержит старт и финиш, а сумма исходных чисел совпадает с ответом. Для поля 15×15 от A1 до O15 посещается 15+15-1=29 клеток. Порядок минимума и максимума берётся из условия.