【代码随想录算法训练营第六十六天|卡码网97.小明逛公园、127.骑士的攻击】

文章目录

• 97.小明逛公园
• 127.骑士的攻击

97.小明逛公园

之前的题目都是只有一个出发点和到达点，这道题是有多个起始对，用之前的算法把每一对结果算出来也是可行的，在这里使用Floyd算法。
本质上是一种动态规划，dp数组dp[i][j][k]中的i，j两点在以(1~k)中的点作为中间结点的时候的最小距离，递推公式是dp[i][j][k]=min(dp[i][k][k-1]+dp[k][j][k-1], dp[i][j][k-1])，遍历顺序是k在最外，i，j在内。本质上是因为dp[i][k][k-1]这些中间量还可能是由k更小的时候的组合推断出来的，所以对于所有的i和j，k都应该是从小到大递增推导所有i和j的状态，所以k在最外层。

n, m = map(int, input().split()) grid = [[[float('inf')] * (n+1) for _ in range(n+1)] for _ in range(n+1)] for i in range(m):     u, v, w = map(int, input().split())     grid[u][v][0] = w     grid[v][u][0] = w  q = int(input()) plans = [] for i in range(q):     start, end = map(int, input().split())     plans.append([start, end])      for k in range(1, n+1):     for i in range(1, n+1):         for j in range(1, n+1):             grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1])   for plan in plans:     if grid[plan[0]][plan[1]][-1] != float('inf'):         print(grid[plan[0]][plan[1]][-1])     else:         print(-1) 

127.骑士的攻击

这道题使用的是Astar算法，是在BFS的基础上进行了一定的优化。普通的BFS也能做但是在广度搜索的时候会有很多的浪费，因此关键就在于每次如何选择朝向目标移动的最近的点。Astar通过计算每个点的预估距离并用小顶堆进行排序，从而使得每次取出来的都是当前可能最小距离的点。在这题使用欧氏距离最合适，总距离是点距离原点的欧氏距离加上到目标点的欧氏距离。

import heapq  n = int(input()) directions = [[-2, 1], [-1, 2], [1, 2], [2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1]] Distance = lambda x, y, tar_x, tar_y: (x - tar_x) ** 2 + (y - tar_y) ** 2  class Knight:     def __init__(self, a1, a2, g=0, f=0, h=0):         self.x = a1         self.y = a2         self.g = g         self.f = f          self.h = h          def __lt__(self, k):         return self.f < k.f          def __str__(self):         return f'Knight:{self.x},{self.y}'      def bfs(grid, knight, target):     heap = []     heapq.heappush(heap, knight)     while heap:         cur = heapq.heappop(heap)         if cur.x == target[0] and cur.y == target[1]:             return         for d in directions:             next_x = cur.x + d[0]             next_y = cur.y + d[1]             if next_x < 1 or next_x >= len(grid) or next_y < 1 or next_y >= len(grid[0]):                 continue             if not grid[next_x][next_y]:                 grid[next_x][next_y] = grid[cur.x][cur.y] + 1                 next_knight = Knight(next_x, next_y)                 next_knight.g = cur.g + 5                 next_knight.h = Distance(next_x, next_y, target[0], target[1])                 next_knight.f = next_knight.g + next_knight.h                  heapq.heappush(heap, next_knight)                  for i in range(n):     a1, a2, b1, b2 = map(int, input().split())     grid = [[0] * 1001 for _ in range(1001)]     knight = Knight(a1, a2)     knight.h = Distance(a1, a2, b1, b2)     knight.f = knight.g + knight.h     bfs(grid, knight, [b1, b2])     print(grid[b1][b2])