На сайте acmp.ru добавились 300 новых задач, и сейчас самое время их решить.
И снова задача на графы, и снова маленькие ограничения, поэтому можно легко решить на Python. Почему на графы? Потому что можно представить, что каждое состояние на доске - это вершина граф, а возможные ходы из этого состояния - рёбра. В таком представлении получаем, что надо найти длину кратчайшего пути между двумя вершинами графа. Для этого можно использовать поиск в ширину (BFS), потому что граф не взвешенный.
Для начала поймём, как будем хранить состояния. Для оптимальности с точки зрения времени и памяти надо каждое состояние кодировать каким-то числом. Но при таких ограничениях в этом нет нужды, поэтому будем хранить одной строкой из 9 символов, просто склеив строки доски.
И сразу после этого можно запустить bfs:
Здесь всё стандартно: есть очередь на обработку, есть словарь used, в котором храним результат для всех обработанных вершин, и для каждой следующей вершины проверяем всех её соседей. А соседей находим с помощью генератора steps:
Итого, два с половиной десятка строк, и решение задачи на 54% сложности готово.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
