2023-08-16：用 go 语言如何解决进击的骑士算法问题呢？

作者：福大大架构师每日一题

2023-08-16
北京
本文字数：4238 字
阅读完需：约 14 分钟

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<Ordering> {        Some(self.cmp(other))    }}
fn min_knight_moves(x: i32, y: i32) -> i32 {    let mut heap = BinaryHeap::new();    let mut closed: HashMap<i32, HashMap<i32, bool>> = HashMap::new();    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<i32, HashMap<i32, bool>>, r: i32, c: i32) -> bool {    if let Some(cols) = closed.get(&r) {        if let Some(&popped) = cols.get(&c) {            return popped;        }    }    false}
fn close(closed: &mut HashMap<i32, HashMap<i32, bool>>, r: i32, c: i32) {    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<i32, HashMap<i32, bool>>,    heap: &mut BinaryHeap<KnightMove>,) {    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 <cmath>#include <iostream>#include <vector>#include <queue>#include <unordered_map>#include <unordered_set>
using namespace std;
bool isPoped(unordered_map<int, unordered_set<int>>& closed, int r, int c) {    return closed.count(r) && closed[r].count(c);}
void close(unordered_map<int, unordered_set<int>>& closed, int r, int c) {    if (!closed.count(r)) {        closed[r] = unordered_set<int>();    }    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<int, unordered_set<int>>& closed,    priority_queue<vector<int>, vector<vector<int>>, greater<>>& heap) {    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<vector<int>, vector<vector<int>>, greater<>> heap;    unordered_map<int, unordered_set<int>> closed;    heap.push({ 0, distance(0, 0, x, y), 0, 0 });    int ans = INT_MAX;    while (!heap.empty()) {        vector<int> cur = heap.top();        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;}