代码随想录算法训练营第五十三天 | Floyd 算法 A * 算法

package main import ( "bufio" "fmt" "os" ) const INF = 10005 func min(a, b int) int { if a < b { return a } return b } func main() { in := bufio.NewReader(os.Stdin) var n, m int fmt.Fscan(in, &n, &m) // grid[i][j] 表示 i -> j 的最短距离 grid := make([][]int, n+1) for i := 0; i <= n; i++ { grid[i] = make([]int, n+1) for j := 0; j <= n; j++ { grid[i][j] = INF } } for i := 0; i < m; i++ { var p1, p2, val int fmt.Fscan(in, &p1, &p2, &val) grid[p1][p2] = val grid[p2][p1] = val // 无向图 } // Floyd-Warshall for k := 1; k <= n; k++ { for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { if grid[i][k]+grid[k][j] < grid[i][j] { grid[i][j] = grid[i][k] + grid[k][j] } } } } var q int fmt.Fscan(in, &q) for q > 0 { q-- var start, end int fmt.Fscan(in, &start, &end) if grid[start][end] == INF { fmt.Println(-1) } else { fmt.Println(grid[start][end]) } } }

package main import ( "bufio" "container/heap" "fmt" "os" ) const N = 1000 var ( moves [N + 1][N + 1]int dir = [8][2]int{ {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, } b1, b2 int ) /* F = G + H G = 起点到当前节点的代价 H = 当前节点到终点的启发式估计 */ type Knight struct { x, y int g, h int f int } /*************** 优先队列实现 ***************/ type PriorityQueue []Knight func (pq PriorityQueue) Len() int { return len(pq) } // 注意：Go 的 heap 是最小堆，这里要让 f 小的优先 func (pq PriorityQueue) Less(i, j int) bool { return pq[i].f < pq[j].f } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] } func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Knight)) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] *pq = old[:n-1] return item } /*************** A* 相关 ***************/ // 启发函数：欧氏距离平方（不开根号） func heuristic(k Knight) int { dx := k.x - b1 dy := k.y - b2 return dx*dx + dy*dy } func astar(start Knight) { pq := &PriorityQueue{} heap.Init(pq) heap.Push(pq, start) for pq.Len() > 0 { cur := heap.Pop(pq).(Knight) if cur.x == b1 && cur.y == b2 { return } for i := 0; i < 8; i++ { nx := cur.x + dir[i][0] ny := cur.y + dir[i][1] if nx < 1 || nx > N || ny < 1 || ny > N { continue } if moves[nx][ny] == 0 { moves[nx][ny] = moves[cur.x][cur.y] + 1 next := Knight{ x: nx, y: ny, g: cur.g + 5, // 马走日：1^2 + 2^2 = 5 } next.h = heuristic(next) next.f = next.g + next.h heap.Push(pq, next) } } } } func main() { in := bufio.NewReader(os.Stdin) var t int fmt.Fscan(in, &t) for t > 0 { t-- var a1, a2 int fmt.Fscan(in, &a1, &a2, &b1, &b2) // 清空 moves for i := 1; i <= N; i++ { for j := 1; j <= N; j++ { moves[i][j] = 0 } } start := Knight{ x: a1, y: a2, g: 0, } start.h = heuristic(start) start.f = start.g + start.h astar(start) fmt.Println(moves[b1][b2]) } }