2023-08-16：用go語言如何解決進擊的騎士算法問題呢？
2023-08-16：用go寫算法。一個坐標可以從 -infinity 延伸到 +infinity 的 無限大的 棋盤上，
你的 騎士 駐扎在坐標為 [0, 0] 的方格里。
騎士的走法和中國象棋中的馬相似，走 “日” 字：
即先向左（或右）走 1 格，再向上（或下）走 2 格，
或先向左（或右）走 2 格，再向上（或下）走 1 格，
每次移動，他都可以像中國象棋中的馬一樣，選八個方向中的一個前進。
返回 騎士前去征服坐標為 [x, y] 的部落所需的最小移動次數(shù)。
本題確保答案是一定存在的。
輸入：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、谷歌、亞馬遜、領(lǐng)英、英偉達。
來自左程云。
答案2023-08-16：
大體步驟如下：
1.初始化一個二叉堆（binary heap）和一個哈希表（hashmap）用于存儲已訪問的位置。
2.將起始位置 [0, 0] 添加到二叉堆中，并初始化最小移動次數(shù)為無窮大。
3.進入循環(huán)，直到二叉堆為空：
??彈出堆頂位置，獲取當前位置的代價、行號和列號。
??檢查當前位置是否已經(jīng)訪問過，如果是則跳過該位置。
??檢查當前位置是否達到目標位置，如果是則更新最小移動次數(shù)為當前代價，并結(jié)束循環(huán)。
??標記當前位置為已訪問。
??嘗試向八個方向移動，將可行的新位置添加到二叉堆中。
4.返回最小移動次數(shù)。
總的時間復(fù)雜度：在最壞情況下，需要訪問所有格子，每次訪問需要將新位置添加到二叉堆中，時間復(fù)雜度為O(N log N)，其中N是需要訪問的格子數(shù)量。
總的額外空間復(fù)雜度：使用了二叉堆和哈希表來存儲已訪問的位置，額外空間復(fù)雜度為O(N)，其中N是需要訪問的格子數(shù)量。
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};
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++完整代碼如下：
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;
}
