Задачи
April 4, 2022

Ход конем - 2

Задача: дана бесконечная шахматная доска (-∞, ∞), а также конь на поле с координатами [0, 0].

Необходимо вернуть минимальное количество шагов, необходимых для перестановки коня на заданное поле [x, y].

Справка: у коня на бесконечной шахматной доске есть 8 возможных ходов.

Примечание: гарантируется, что ответ существует.

Примеры:

  1. x = 2, y = 1
    Output: 1
    Пояснение: [0, 0] -> [2, 1]
  2. x = 5, y = 5
    Output: 4
    Пояснение: [0, 0] -> [2, 1] -> [4, 2] -> [3, 4] -> [5, 5]

Разбор

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

Поэтому мы можем утверждать, что как только мы достигнем конечной точки, мы можем назвать текущий путь кратчайшим, т.к. наш поиск соот-т порядку расстояния.

Реализация

Play-test

https://dotnetfiddle.net/1QrGEh