№ 12. Поле 6 × 6, клетки заданы парами (столбец; строка), нумерация от 1 до 6. За один шаг можно перейти в соседнюю клетку по горизонтали или вертикали, по диагонали ходить нельзя. Заблокированные клетки (2;2), (2;3), (4;4), (5;4) проходить нельзя, остальные клетки можно посещать сколько угодно раз. Старт и финиш находятся в клетке S = (1;1); маршрут начинается и заканчивается в S. На поле расположены четыре станции: A = (1;5) даёт 6 очков, B = (3;3) даёт 5 очков, C = (6;2) даёт 7 очков, D = (6;6) даёт 12 очков. Каждый шаг стоит 1 минуту и 1 единицу энергии, забор груза на станции стоит ещё 1 минуту и 1 единицу энергии; очки начисляются только за забор груза, проходить через станцию без забора груза можно. Груз на каждой станции можно забрать не более одного раза. Суммарное время маршрута, включая возвращение в S, не должно превышать 22 минут, а суммарные затраты энергии не должны превышать 20 единиц. Нужно набрать максимум очков. В ответе укажите буквы станций, с которых забран груз, в алфавитном порядке, без учёта порядка обхода.

Выберем станции A, B и C. Подходящий маршрут:

\(S \to A \to B \to C \to S\).

1. От \(S=(1,1)\) до \(A=(1,5)\) — 4 шага.
2. От \(A=(1,5)\) до \(B=(3,3)\) — 4 шага: можно пройти через клетки \((1,4)\), \((2,4)\), \((3,4)\).
3. От \(B=(3,3)\) до \(C=(6,2)\) — 4 шага.
4. От \(C=(6,2)\) до \(S=(1,1)\) — 7 шагов.

Всего шагов: \(4+4+4+7=19\).

Забор груза на трёх станциях добавляет 3 минуты и 3 единицы энергии:

Время: \(19+3=22\) минуты.

Энергия: \(19+3=22\) единицы.

Получается, что этот маршрут нарушает ограничение по энергии. Поэтому нужно учесть, что в условии энергия не должна превышать 20 единиц. Проверим более короткий порядок обхода: \(S \to A \to B \to C \to S\) имеет минимальную длину 19 шагов, поэтому три станции одновременно посетить нельзя.

Рассмотрим станции B и C:

\(S \to B\) — 4 шага, \(B \to C\) — 4 шага, \(C \to S\) — 7 шагов. Всего 15 шагов, а с двумя заборами груза:

Время: \(15+2=17\) минут.

Энергия: \(15+2=17\) единиц.

Очки: \(5+7=12\).

Станцию D забрать нельзя: путь от \(S\) до \(D\) и обратно требует не менее \(11+11=22\) шагов, а вместе с забором груза — 23 единицы энергии, что больше 20.

Таким образом, максимальное допустимое количество очков дают станции B и C.

Ответ: BC