Несложная задача про написание обхода в ширину, на которой можно потренировать и применить несколько трюков. Читаем условие:
В этой задаче нужно построить кратчайший путь, поэтому это явно поиск в ширину или BFS. Этот алгоритм подробно разбирали при решении Задачи 127. Путь. Если вы с ним не знакомы, то рекомендую сначала прочитать тот разбор.
По условию задачи, поле очень маленькое (помним, что алгоритм BFS работает за линейное время от количества вершин и рёбер в графе, то есть O(V + E)). Поэтому, в качестве разнообразия, напишем поиск в ширину без использования очереди, пожертвовав алгоритмической оптимальностью.
Но для начала надо считать данные:
Писать поиск в ширину на строках очень неудобно, поэтому заведём числовой двумерный массив. А также воспользуемся барьерным методом - сделаем массив на два ряда больше в каждую сторону (которые заполнил стенками), тогда ни один ход коня не приведёт к выходу за границы массива.
Два конца пути, заданные во входных данных обработаем следующим образом:
- координаты первого запомним, чтобы потом проверить, что дошли до него,
- в координаты второго поставим единичку, в качестве инициализации поиска в ширину.
По аналогии с Задачей 690. Конная прогулка заведём список всех ходов коня, чтобы было проще перебирать следующие состояния:
Теперь, когда все данные подготовлены, можно запустить поиск в ширину. На каждой итерации будем поддерживать её номер, что будет также и номером шага коня. А также будет логическая переменная, отвечающая, что на текущем шаге были сделаны ходы:
Заметим, что проходы идут не по всему двумерному массиву, а с отступом в два ряда от каждого края, потому что именно там находится реальное поле, а за его границами стоят стенки из -1. И благодаря этому во вложенном условии нам не надо писать проверок на выход за границы массива.
После этого в массиве в каждой клетке будет стоять количество ходов, которые потребуются коню, чтобы до неё добраться. Или 0, если до неё нельзя дойти (или путь длиннее, чем до финальной точки).
Так как поиск в ширину является алгоритмом динамического программирования, чтобы построить путь, надо пройти с конца (также, как и в
Задаче 707. Zuma):
Из-за неудобного формата вывода, к сожалению, приходится числовой массив обратно преобразовывать в строки. А ещё, в очередной раз, барьерный метод помогает нам не писать дополнительные проверки.
В этом разборе мы познакомились с ещё одним вариантом реализации алгоритма поиска в ширину. А также применили барьерный метод.
Предыдущий выпуск: Задача 350. Перестановки
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.