Увімкніть лампу#125

Увімкніть лампу (Editorial)

Зручно дивитися не на плитки, а на кути плиток. Вони утворюють сітку розміром (N+1) \times (M+1); живлення підключене до вузла , лампа — до вузла (N, M).

Дріт кожної плитки з'єднує два її протилежні кути, тобто дозволяє перейти по діагоналі всередині цієї плитки. Плитка з'єднує лівий верхній кут з правим нижнім, плитка — правий верхній з лівим нижнім. Поворот плитки на міняє один варіант на інший і коштує одну операцію.

Отже, будуємо граф на вузлах сітки: з вузла можна перейти в будь-який з чотирьох діагональних сусідів, проходячи крізь відповідну плитку. Вага ребра дорівнює , якщо дріт цієї плитки вже з'єднує потрібну пару кутів, і — якщо плитку доведеться повернути. Задача звелася до пошуку найкоротшого шляху з у (N,M).

Оскільки всі ваги — нулі та одиниці, найшвидший спосіб — 0-1 BFS: замість черги з пріоритетами беремо двобічну чергу (deque), ребра ваги додаємо в її початок, ребра ваги — у кінець. Це дає замість \mathcal{O}(NM \log NM) у Дейкстри.

Окремо треба обробити випадок, коли шляху не існує. Кожен крок змінює суму координат вузла на парне число, тому парність суми r + c зберігається. Старт має суму , фініш — N + M. Якщо N + M непарне, дістатися до лампи неможливо взагалі, і треба вивести NO SOLUTION.

Якщо ж N + M парне, шлях завжди існує (у крайньому разі повернувши всі потрібні плитки), і відповідь — знайдена відстань.