Дуэль художниц

Музей имеет форму равностороннего треугольника со стороной side, разбитого на side² одинаковых треугольных комнат. Комната задаётся парой [r, p]: ряд r от 1 до side сверху вниз и позиция p от 1 до 2r - 1 слева направо. Комнаты с нечётным p смотрят вершиной вверх, с чётным — вниз. Двери есть только между комнатами с общей стороной: [r, p] и [r, p + 1] соседние, а комната с нечётным p при r < side ещё соседствует с [r + 1, p + 1] под ней.

Альма стоит в комнате alma, Берта — в другой комнате berthe; свои стартовые комнаты обе уже покрасили. Комнаты из списка blocked закрыты на ремонт: туда входить нельзя. Художницы ходят по очереди, первой Альма. В свой ход художница обязана перейти в соседнюю непокрашенную незакрытую комнату и покрасить её; если такой нет, она пропускает ход. Игра кончается, когда не может ходить ни одна. Счёт — число комнат, покрашенных Альмой, минус число комнат Берты (стартовые учитываются). Альма играет на максимум счёта, Берта — на минимум, обе оптимально. Верните итоговый счёт.

Ограничения: 2 ≤ side ≤ 6; стартовые и закрытые комнаты различны.

Пример: 2, [1, 1], [2, 1], [] → 2 (Альма идёт в [2, 2], затем в [2, 3], а Берта заперта).

Источник: Coding Competitions Archive, kickstart/2020/round_f/painters_duel · © Google LLC · Apache-2.0 · условие переведено и дополнено