Размер:
A A A
Цвет: C C C
Изображения Вкл.Выкл.
Обычная версия сайта
Demidov Yaroslavl State University

Один день - одна задача. Пешка туда - сюда

Aa
03.11.2020
Один день - одна задача. Пешка туда - сюда Недавно закончился квалификационный раунд, где командам было предложено 12 задач. Лучшие команды решили все задачи этого раунда, однако были команды, которым это не удалось.

Становиться лучше можно путем ежедневных тренировок. Поэтому вы можете участвовать в тренировке на платформе Codeforces c задачами квалификации и решать по одной задачке в день

https://codeforces.com/gym/102775


Мы начнем наш разбор с задачи H. Пешка туда-сюда? Рассмотрим граф, соответствующий шахматной доске. Тогда вершинами будут её клетки, а ребра между вершинами будут существовать тогда и только тогда, когда обе клетки являются доступными для посещения. Тогда в этом графе требуется найти кратчайший путь из вершины (x1, y1) в вершину (x2,y2). Это можно сделать поиском в ширину. Если кратчайшего пути нет, то выведем на экран −1.

Возврат к списку