2023-08-16：用go写算法。一个坐标可以从 -infinity 延伸到 +infinity 的 无限大的 棋盘上，
你的 骑士 驻扎在坐标为 [0, 0] 的方格里。
骑士的走法和中国象棋中的马相似，走 “日” 字：
即先向左（或右）走 1 格，再向上（或下）走 2 格，
或先向左（或右）走 2 格，再向上（或下）走 1 格，
每次移动，他都可以像中国象棋中的马一样，选八个方向中的一个前进。
返回 骑士前去征服坐标为 [x, y] 的部落所需的最小移动次数。
本题确保答案是一定存在的。
输入：x = 2, y = 1。
输出：1。
解释：[0, 0] → [2, 1]。
输入：x = 5, y = 5。
输出：4。
解释：[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]。
提示：|x| + |y| <= 300。
来自Indeed、谷歌、亚马逊、领英、英伟达。
来自左程云。
答案2023-08-16：
大体步骤如下：
1.初始化一个二叉堆（binary heap）和一个哈希表（hashmap）用于存储已访问的位置。
2.将起始位置 [0, 0] 添加到二叉堆中，并初始化最小移动次数为无穷大。
3.进入循环，直到二叉堆为空：
弹出堆顶位置，获取当前位置的代价、行号和列号。
检查当前位置是否已经访问过，如果是则跳过该位置。
检查当前位置是否达到目标位置，如果是则更新最小移动次数为当前代价，并结束循环。
标记当前位置为已访问。
尝试向八个方向移动，将可行的新位置添加到二叉堆中。
4.返回最小移动次数。
总的时间复杂度：在最坏情况下，需要访问所有格子，每次访问需要将新位置添加到二叉堆中，时间复杂度为O(N log N)，其中N是需要访问的格子数量。
总的额外空间复杂度：使用了二叉堆和哈希表来存储已访问的位置，额外空间复杂度为O(N)，其中N是需要访问的格子数量。
go完整代码如下：
package main
import (
"fmt"
"math"
"github.com/emirpasic/gods/maps/hashmap"
"github.com/emirpasic/gods/sets/hashset"
"github.com/emirpasic/gods/trees/binaryheap"
)
// minKnightMoves calculates the minimum number of moves required for a knight to reach position (x, y).
func minKnightMoves(x, y int) int {
heap := binaryheap.NewWith(func(a, b interface{}) int {
return int(a.([]int)[0] + a.([]int)[1] - b.([]int)[0] - b.([]int)[1])
})
closed := hashmap.New()
heap.Push([]int{0, distance(0, 0, x, y), 0, 0})
ans := math.MaxInt32
for heap.Size() > 0 {
c, _ := heap.Pop()
cur := c.([]int)
cost := cur[0]
row := cur[2]
col := cur[3]
if isClosed(closed, row, col) {
continue
}
if row == x && col == y {
ans = cost
break
}
close(closed, row, col)
add(cost+1, row+2, col+1, x, y, closed, heap)
add(cost+1, row+1, col+2, x, y, closed, heap)
add(cost+1, row-1, col+2, x, y, closed, heap)
add(cost+1, row-2, col+1, x, y, closed, heap)
add(cost+1, row-2, col-1, x, y, closed, heap)
add(cost+1, row-1, col-2, x, y, closed, heap)
add(cost+1, row+1, col-2, x, y, closed, heap)
add(cost+1, row+2, col-1, x, y, closed, heap)
}
return ans
}
// isClosed checks if the position (r, c) has been visited before.
func isClosed(closed *hashmap.Map, r, c int) bool {
set, found := closed.Get(r)
if !found {
return false
}
return set.(*hashset.Set).Contains(c)
}
// close adds the position (r, c) to the closed set.
func close(closed *hashmap.Map, r, c int) {
set, found := closed.Get(r)
if !found {
set = hashset.New()
closed.Put(r, set)
}
set.(*hashset.Set).Add(c)
}
// add adds the position (r, c) to the heap if it hasn't been visited before.
func add(cost, r, c, x, y int, closed *hashmap.Map, heap *binaryheap.Heap) {
if !isClosed(closed, r, c) {
heap.Push([]int{cost, distance(r, c, x, y), r, c})
}
}
// distance calculates the Manhattan distance divided by 3.
// This is used as the heuristic function for estimating the cost.
func distance(r, c, x, y int) int {
return (int(math.Abs(float64(x-r))) + int(math.Abs(float64(y-c)))) / 3
}
func main() {
x, y := 2, 1
result := minKnightMoves(x, y)
fmt.Println(result)
}
rust完整代码如下：
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap};
#[derive(Copy, Clone, Eq, PartialEq)]
struct KnightMove {
cost: i32,
distance: i32,
row: i32,
col: i32,
}
impl Ord for KnightMove {
fn cmp(&self, other: &Self) -> Ordering {
(self.cost + self.distance)
.cmp(&(other.cost + other.distance))
.reverse()
}
}
impl PartialOrd for KnightMove {
fn partial_cmp(&self, other: &Self) -> Option
Some(self.cmp(other))
}
}
fn min_knight_moves(x: i32, y: i32) -> i32 {
let mut heap = BinaryHeap::new();
let mut closed: HashMap
heap.push(KnightMove {
cost: 0,
distance: distance(0, 0, x, y),
row: 0,
col: 0,
});
let mut ans = i32::MAX;
while let Some(cur) = heap.pop() {
let cost = cur.cost;
let row = cur.row;
let col = cur.col;
if is_popped(&closed, row, col) {
continue;
}
if row == x && col == y {
ans = cost;
break;
}
close(&mut closed, row, col);
add(cost + 1, row + 2, col + 1, x, y, &mut closed, &mut heap);
add(cost + 1, row + 1, col + 2, x, y, &mut closed, &mut heap);
add(cost + 1, row - 1, col + 2, x, y, &mut closed, &mut heap);
add(cost + 1, row - 2, col + 1, x, y, &mut closed, &mut heap);
add(cost + 1, row - 2, col - 1, x, y, &mut closed, &mut heap);
add(cost + 1, row - 1, col - 2, x, y, &mut closed, &mut heap);
add(cost + 1, row + 1, col - 2, x, y, &mut closed, &mut heap);
add(cost + 1, row + 2, col - 1, x, y, &mut closed, &mut heap);
}
ans
}
fn is_popped(closed: &HashMap
if let Some(cols) = closed.get(&r) {
if let Some(&popped) = cols.get(&c) {
return popped;
}
}
false
}
fn close(closed: &mut HashMap
let cols = closed.entry(r).or_default();
cols.insert(c, true);
}
fn add(
cost: i32,
r: i32,
c: i32,
x: i32,
y: i32,
closed: &mut HashMap
heap: &mut BinaryHeap
) {
if !is_popped(closed, r, c) {
heap.push(KnightMove {
cost,
distance: distance(r, c, x, y),
row: r,
col: c,
});
}
}
fn distance(r: i32, c: i32, x: i32, y: i32) -> i32 {
(i32::abs(x - r) + i32::abs(y - c)) / 3
}
fn main() {
let x = 2;
let y = 1;
let result = min_knight_moves(x, y);
println!("Minimum knight moves: {}", result);
}
c++完整代码如下：
#include
#include
#include
#include
#include
#include
using namespace std;
bool isPoped(unordered_map
return closed.count(r) && closed[r].count(c);
}
void close(unordered_map
if (!closed.count(r)) {
closed[r] = unordered_set
}
closed[r].insert(c);
}
int distance(int r, int c, int x, int y);
void add(int cost, int r, int c, int x, int y, unordered_map
priority_queue
if (!isPoped(closed, r, c)) {
heap.push({ cost, distance(r, c, x, y), r, c });
}
}
int distance(int r, int c, int x, int y) {
return (abs(x - r) + abs(y - c)) / 3;
}
int minKnightMoves(int x, int y) {
priority_queue
unordered_map
heap.push({ 0, distance(0, 0, x, y), 0, 0 });
int ans = INT_MAX;
while (!heap.empty()) {
vector
heap.pop();
int cost = cur[0];
int row = cur[2];
int col = cur[3];
if (isPoped(closed, row, col)) {
continue;
}
if (row == x && col == y) {
ans = cost;
break;
}
close(closed, row, col);
add(cost + 1, row + 2, col + 1, x, y, closed, heap);
add(cost + 1, row + 1, col + 2, x, y, closed, heap);
add(cost + 1, row - 1, col + 2, x, y, closed, heap);
add(cost + 1, row - 2, col + 1, x, y, closed, heap);
add(cost + 1, row - 2, col - 1, x, y, closed, heap);
add(cost + 1, row - 1, col - 2, x, y, closed, heap);
add(cost + 1, row + 1, col - 2, x, y, closed, heap);
add(cost + 1, row + 2, col - 1, x, y, closed, heap);
}
return ans;
}
int main() {
int x = 2;
int y = 1;
int result = minKnightMoves(x, y);
cout << "Minimum number of knight moves: " << result << endl;
return 0;
}
参考阅读
发表评论