На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0].
У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении.
return минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует.
例:
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
C# 解法
照合済み/オリジナル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];
}
}
}
}
}C++ 解法
自動ドラフト、提出前に確認#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
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 unordered_map<string, int> {{"0,0", 0}};
var targetQueue = new queue<int[]>();
targetQueue.Enqueue(new int[] {x, y, 0});
var targetDistance = new unordered_map<string, int> {{$"{x},{y}", 0}};
while (true) {
var origin = originQueue.Dequeue();
var originKey = $"{origin[0]},{origin[1]}";
if (targetDistance.count(originKey)) {
return origin[2] + targetDistance[originKey];
}
var target = targetQueue.Dequeue();
var targetKey = $"{target[0]},{target[1]}";
if (originDistance.count(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.count(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.count(nextTargetKey)) {
targetQueue.Enqueue(nextTarget);
targetDistance[nextTargetKey] = nextTarget[2];
}
}
}
}
}Java 解法
照合済み/オリジナルclass Solution {
public int minKnightMoves(int x, int y) {
int[][] offsets = {{1, 2}, {2, 1}, {2, -1}, {1, -2},
{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
Deque<int[]> originQueue = new LinkedList<>();
originQueue.addLast(new int[]{0, 0, 0});
Map<String, Integer> originDistance = new HashMap<>();
originDistance.put("0,0", 0);
Deque<int[]> targetQueue = new LinkedList<>();
targetQueue.addLast(new int[]{x, y, 0});
Map<String, Integer> targetDistance = new HashMap<>();
targetDistance.put(x + "," + y, 0);
while (true) {
int[] origin = originQueue.removeFirst();
String originXY = origin[0] + "," + origin[1];
if (targetDistance.containsKey(originXY)) {
return origin[2] + targetDistance.get(originXY);
}
int[] target = targetQueue.removeFirst();
String targetXY = target[0] + "," + target[1];
if (originDistance.containsKey(targetXY)) {
return target[2] + originDistance.get(targetXY);
}
for (int[] offset : offsets) {
int[] nextOrigin = new int[]{origin[0] + offset[0], origin[1] + offset[1]};
String nextOriginXY = nextOrigin[0] + "," + nextOrigin[1];
if (!originDistance.containsKey(nextOriginXY)) {
originQueue.addLast(new int[]{nextOrigin[0], nextOrigin[1], origin[2] + 1});
originDistance.put(nextOriginXY, origin[2] + 1);
}
int[] nextTarget = new int[]{target[0] + offset[0], target[1] + offset[1]};
String nextTargetXY = nextTarget[0] + "," + nextTarget[1];
if (!targetDistance.containsKey(nextTargetXY)) {
targetQueue.addLast(new int[]{nextTarget[0], nextTarget[1], target[2] + 1});
targetDistance.put(nextTargetXY, target[2] + 1);
}
}
}
}
}JavaScript 解法
照合済み/オリジナル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];
}
}
}
}
}Python 解法
照合済み/オリジナルfrom collections import deque
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
offsets = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
origin_queue = deque([(0, 0, 0)])
origin_distance = {"0,0": 0}
target_queue = deque([(x, y, 0)])
target_distance = {f"{x},{y}": 0}
while True:
ox, oy, od = origin_queue.popleft()
origin_key = f"{ox},{oy}"
if origin_key in target_distance:
return od + target_distance[origin_key]
tx, ty, td = target_queue.popleft()
target_key = f"{tx},{ty}"
if target_key in origin_distance:
return td + origin_distance[target_key]
for dx, dy in offsets:
next_origin = (ox + dx, oy + dy, od + 1)
next_origin_key = f"{next_origin[0]},{next_origin[1]}"
if next_origin_key not in origin_distance:
origin_queue.append(next_origin)
origin_distance[next_origin_key] = next_origin[2]
next_target = (tx + dx, ty + dy, td + 1)
next_target_key = f"{next_target[0]},{next_target[1]}"
if next_target_key not in target_distance:
target_queue.append(next_target)
target_distance[next_target_key] = next_target[2]Go 解法
照合済み/オリジナルpackage main
import (
"container/list"
"fmt"
)
func minKnightMoves(x int, y int) int {
offsets := [][]int{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}
originQueue := list.New()
originQueue.PushBack([]int{0, 0, 0})
originDistance := map[string]int{"0,0": 0}
targetQueue := list.New()
targetQueue.PushBack([]int{x, y, 0})
targetDistance := map[string]int{fmt.Sprintf("%d,%d", x, y): 0}
for {
origin := originQueue.Remove(originQueue.Front()).([]int)
originKey := fmt.Sprintf("%d,%d", origin[0], origin[1])
if targetDistance[originKey] != 0 || originKey == fmt.Sprintf("%d,%d", x, y) {
return origin[2] + targetDistance[originKey]
}
target := targetQueue.Remove(targetQueue.Front()).([]int)
targetKey := fmt.Sprintf("%d,%d", target[0], target[1])
if originDistance[targetKey] != 0 || targetKey == "0,0" {
return target[2] + originDistance[targetKey]
}
for _, offset := range offsets {
nextOrigin := []int{origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1}
nextOriginKey := fmt.Sprintf("%d,%d", nextOrigin[0], nextOrigin[1])
if _, ok := originDistance[nextOriginKey]; !ok {
originQueue.PushBack(nextOrigin)
originDistance[nextOriginKey] = nextOrigin[2]
}
nextTarget := []int{target[0] + offset[0], target[1] + offset[1], target[2] + 1}
nextTargetKey := fmt.Sprintf("%d,%d", nextTarget[0], nextTarget[1])
if _, ok := targetDistance[nextTargetKey]; !ok {
targetQueue.PushBack(nextTarget)
targetDistance[nextTargetKey] = nextTarget[2]
}
}
}
}Algorithm
Инициализация структур данных:
Инициализируйте две очереди для хранения координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.
Инициализируйте две карты для хранения посещенных координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.
実装 двунаправленного поиска в ширину (BFS):
Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки.
Если круги пересекаются, возвращайте сумму расстояний до точки пересечения.
Расширение кругов поиска:
Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня.
Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены.
Увеличивайте units на значение, извлеченное из кучи.
😎
Vacancies for this task
有効な求人 with overlapping task tags are 表示.
有効な求人はまだありません。