Задача: 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 на значение, извлеченное из кучи.

😎 Решение:

class Solution {
    minKnightMoves(x, y) {
        const offsets = [
            [1, 2], [2, 1], [2, -1], [1, -2],
            [-1, -2], [-2, -1], [-2, 1], [-1, 2]
        ];

        const originQueue = [[0, 0, 0]];
        const originDistance = { '0,0': 0 };

        const targetQueue = [[x, y, 0]];
        const targetDistance = { [`${x},${y}`]: 0 };

        while (true) {
            const [ox, oy, od] = originQueue.shift();
            const originKey = `${ox},${oy}`;
            if (originKey in targetDistance) {
                return od + targetDistance[originKey];
            }

            const [tx, ty, td] = targetQueue.shift();
            const targetKey = `${tx},${ty}`;
            if (targetKey in originDistance) {
                return td + originDistance[targetKey];
            }

            for (const [dx, dy] of offsets) {
                const nextOrigin = [ox + dx, oy + dy, od + 1];
                const nextOriginKey = `${nextOrigin[0]},${nextOrigin[1]}`;
                if (!(nextOriginKey in originDistance)) {
                    originQueue.push(nextOrigin);
                    originDistance[nextOriginKey] = nextOrigin[2];
                }

                const nextTarget = [tx + dx, ty + dy, td + 1];
                const nextTargetKey = `${nextTarget[0]},${nextTarget[1]}`;
                if (!(nextTargetKey in targetDistance)) {
                    targetQueue.push(nextTarget);
                    targetDistance[nextTargetKey] = nextTarget[2];
                }
            }
        }
    }
}

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