Секция

Сетка и графы

Поворот матрицы, острова, кратчайший путь и курсы с зависимостями. Сетку обходят в ширину или в глубину, курсы — топологической сортировкой.

Код можно запускать, разбор открыт. Внутри шага задачи усложняются, следующий шаг уже про другую формулировку.

Создайте аккаунт, чтобы видеть прогресс по треку.

Шаг 1. Матрица на месте

Поворот на 90 градусов и обнуление строк со столбцами. Затем проверка судоку: отдельные ограничения на строки, столбцы и квадраты 3×3.

Число компонент, острова на сетке, кратчайший путь без весов и гниющие фрукты. Фрукты — обход в ширину сразу из всех испорченных клеток.

Сначала любой порядок прохождения. Затем ответ, можно ли закончить все курсы: это поиск цикла в том же графе.