Задача: 1197. Minimum Knight Moves
Сложность: medium

На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0].
У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении.

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

Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

👨‍💻 Алгоритм:

1⃣Инициализация структур данных:
Инициализируйте две очереди для хранения координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.
Инициализируйте две карты для хранения посещенных координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.

2⃣Реализация двунаправленного поиска в ширину (BFS):
Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки.
Если круги пересекаются, возвращайте сумму расстояний до точки пересечения.

3⃣ Расширение кругов поиска:
Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня.
Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены.
Увеличивайте units на значение, извлеченное из кучи.

😎 Решение:

public class Solution {
    public int MinKnightMoves(int x, int y) {
        int[][] offsets = new int[][] {
            new int[] {1, 2}, new int[] {2, 1}, new int[] {2, -1}, new int[] {1, -2},
            new int[] {-1, -2}, new int[] {-2, -1}, new int[] {-2, 1}, new int[] {-1, 2}
        };
        
        var originQueue = new Queue<int[]>();
        originQueue.Enqueue(new int[] {0, 0, 0});
        var originDistance = new Dictionary<string, int> {{"0,0", 0}};
        
        var targetQueue = new Queue<int[]>();
        targetQueue.Enqueue(new int[] {x, y, 0});
        var targetDistance = new Dictionary<string, int> {{$"{x},{y}", 0}};
        
        while (true) {
            var origin = originQueue.Dequeue();
            var originKey = $"{origin[0]},{origin[1]}";
            if (targetDistance.ContainsKey(originKey)) {
                return origin[2] + targetDistance[originKey];
            }
            
            var target = targetQueue.Dequeue();
            var targetKey = $"{target[0]},{target[1]}";
            if (originDistance.ContainsKey(targetKey)) {
                return target[2] + originDistance[targetKey];
            }
            
            foreach (var offset in offsets) {
                var nextOrigin = new int[] {origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1};
                var nextOriginKey = $"{nextOrigin[0]},{nextOrigin[1]}";
                if (!originDistance.ContainsKey(nextOriginKey)) {
                    originQueue.Enqueue(nextOrigin);
                    originDistance[nextOriginKey] = nextOrigin[2];
                }
                
                var nextTarget = new int[] {target[0] + offset[0], target[1] + offset[1], target[2] + 1};
                var nextTargetKey = $"{nextTarget[0]},{nextTarget[1]}";
                if (!targetDistance.ContainsKey(nextTargetKey)) {
                    targetQueue.Enqueue(nextTarget);
                    targetDistance[nextTargetKey] = nextTarget[2];
                }
            }
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний