Задачи
April 4, 2022
Ход конем - 2
Задача: дана бесконечная шахматная доска (-∞, ∞), а также конь на поле с координатами [0, 0].
Необходимо вернуть минимальное количество шагов, необходимых для перестановки коня на заданное поле [x, y].
Справка: у коня на бесконечной шахматной доске есть 8 возможных ходов.
Примечание: гарантируется, что ответ существует.
- x = 2, y = 1
Output: 1
Пояснение: [0, 0] -> [2, 1] - x = 5, y = 5
Output: 4
Пояснение: [0, 0] -> [2, 1] -> [4, 2] -> [3, 4] -> [5, 5]
Разбор
Ключ к решению этой проблемы основан на стратегии BFS. С помощью BFS мы гарантируем, что, прежде чем двигаться дальше к конечной точке, все ближайшие точки мы уже проверим.
Поэтому мы можем утверждать, что как только мы достигнем конечной точки, мы можем назвать текущий путь кратчайшим, т.к. наш поиск соот-т порядку расстояния.