Задача: 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 {
    fun minKnightMoves(x: Int, y: Int): Int {
        val offsets = arrayOf(
            intArrayOf(1, 2), intArrayOf(2, 1), intArrayOf(2, -1), intArrayOf(1, -2),
            intArrayOf(-1, -2), intArrayOf(-2, -1), intArrayOf(-2, 1), intArrayOf(-1, 2)
        )
        
        val originQueue: Deque<IntArray> = LinkedList()
        originQueue.add(intArrayOf(0, 0, 0))
        val originDistance = mutableMapOf("0,0" to 0)
        
        val targetQueue: Deque<IntArray> = LinkedList()
        targetQueue.add(intArrayOf(x, y, 0))
        val targetDistance = mutableMapOf("$x,$y" to 0)
        
        while (true) {
            val origin = originQueue.removeFirst()
            val originKey = "${origin[0]},${origin[1]}"
            if (targetDistance.containsKey(originKey)) {
                return origin[2] + targetDistance[originKey]!!
            }
            
            val target = targetQueue.removeFirst()
            val targetKey = "${target[0]},${target[1]}"
            if (originDistance.containsKey(targetKey)) {
                return target[2] + originDistance[targetKey]!!
            }
            
            for (offset in offsets) {
                val nextOrigin = intArrayOf(origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1)
                val nextOriginKey = "${nextOrigin[0]},${nextOrigin[1]}"
                if (!originDistance.containsKey(nextOriginKey)) {
                    originQueue.add(nextOrigin)
                    originDistance[nextOriginKey] = nextOrigin[2]
                }
                
                val nextTarget = intArrayOf(target[0] + offset[0], target[1] + offset[1], target[2] + 1)
                val nextTargetKey = "${nextTarget[0]},${nextTarget[1]}"
                if (!targetDistance.containsKey(nextTargetKey)) {
                    targetQueue.add(nextTarget)
                    targetDistance[nextTargetKey] = nextTarget[2]
                }
            }
        }
    }
}

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