🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 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 = LinkedList()
originQueue.add(intArrayOf(0, 0, 0))
val originDistance = mutableMapOf("0,0" to 0)
val targetQueue: Deque = 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]
}
}
}
}
}
Ставь 👍 и забирай 📚 Базу знаний
