qidao123.com技术社区-IT企服评测·应用市场

标题: 代码随想录算法训练营第六十六天| 图论11—卡码网97. 小明逛公园，127. 骑士的攻击 [打印本页]
作者: 石小疯    时间: 昨天 14:52
标题: 代码随想录算法训练营第六十六天| 图论11—卡码网97. 小明逛公园，127. 骑士的攻击
继续补，又是两个新算法，继续举行委曲理解，也是训练营末了一天了，六十多天的刷题告一段落了！

97. 小明逛公园

97. 小明逛公园
感觉还是有点难理解原理
Floyd 算法对边的权值正负没有要求，都可以处置惩罚。核心思想是动态规划。我们求节点1 到 节点9 的最短距离，用二维数组来体现即：grid[1][9]，如果最短距离是10 ，那就是 grid[1][9] = 10。
节点1到节点9 的最短距离可以由 节点1 到节点5的最短距离 + 节点5到节点9的最短距离构成grid[1][9] = grid[1][5] + grid[5][9]。节点1到节点5的最短距离可以节点1到节点3的最短距离 + 节点3 到 节点5 的最短距离构成即 grid[1][5] = grid[1][3] + grid[3][5]
由于代码是DP，所以有种很认识的感觉。首先初始化DP数组。重点是在理解三重循环
最外层k: 中转点选择当前答应使用的中转节点。假设你正在考虑是否可以使用 k 来让路径从 i 到 j 更短。相当于说：如果我答应走“颠末 k”，会不会让i到j更快？后续的i是出发点，j是结束点，开始遍历整个路径。

  1. if __name__ == '__main__':
  2.     max_int = 10005  # 设置最大路径，因为边最大距离为10^4
  4.     n, m = map(int, input().split())
  6.     grid = [[max_int]*(n+1) for _ in range(n+1)]  # 初始化二维dp数组
  8.     for _ in range(m):
  9.         p1, p2, val = map(int, input().split())
  10.         grid[p1][p2] = val
  11.         grid[p2][p1] = val
  13.     # 开始floyd
  14.     for k in range(1, n+1):
  15.         for i in range(1, n+1):
  16.             for j in range(1, n+1):
  17.                 grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])
  19.     # 输出结果
  20.     z = int(input())
  21.     for _ in range(z):
  22.         start, end = map(int, input().split())
  23.         if grid[start][end] == max_int:
  24.             print(-1)
  25.         else:
  26.             print(grid[start][end])
复制代码

127. 骑士的攻击

127. 骑士的攻击
稍微容易理解的一种算法，但是感觉每天花时间去理解两种算法有点脑容量不敷。A（A-Star）算法的路径搜刮实现*，用于求国际象棋中“马”（Knight）从一个点跳到另一个点的最少步数。首先还是定义移动方式，还是有点像DP刚开始的定义，使用欧几里得距离作为启发函数（h(n)），估计当前点到目标点的“直线距离”。这个就是判定路径是否变小的一个依据。移动的算法采用bfs，实际是A 算法 + 优先队列（堆）*的方法。每次在每个点尝试各个方向移动马，同时要举行欧几里得距离判定来看是否距离更短
  1. import heapq
  3. n = int(input())
  5. moves = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]
  7. def distance(a, b):
  8.     return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5
  10. def bfs(start, end):
  11.     q = [(distance(start, end), start)]
  12.     step = {start: 0}
  13.      
  14.     while q:
  15.         d, cur = heapq.heappop(q)
  16.         if cur == end:
  17.             return step[cur]
  18.         for move in moves:
  19.             new = (move[0] + cur[0], move[1] + cur[1])
  20.             if 1 <= new[0] <= 1000 and 1 <= new[1] <= 1000:
  21.                 step_new = step[cur] + 1
  22.                 if step_new < step.get(new, float('inf')):
  23.                     step[new] = step_new
  24.                     heapq.heappush(q, (distance(new, end) + step_new, new))
  25.     return False
  26.                      
  27. for _ in range(n):
  28.     a1, a2, b1, b2 = map(int, input().split())
  29.     print(bfs((a1, a2), (b1, b2)))
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4