本文共 3625 字，大约阅读时间需要 12 分钟。
荆轲刺秦王是一个经典的动力学规划问题，涉及到哈曼顿距离和路径规划。为了解决这个问题，我们将使用广度优先搜索（BFS）来模拟路径探索过程，同时考虑两个技能的使用次数限制。
哈曼顿距离：哈曼顿距离是棋盘距离，计算为|x1 - x2| + |y1 - y2|。护卫看不到自己所在的点以及哈曼顿距离超过某个值的点。
技能使用：普通走法每一步可以走四个方向，闪现可以在一秒内走到原本护卫能看到的地方，但不能走到护卫的位置。两个技能可以同时使用，没有间隔时间，但各有使用次数限制。
优先级：优先选步数最少的，步数相同选技能次数最少的，技能次数相同选隐身次数最少的。
预处理护卫可见区域：使用差分方法计算每个点是否被任何护卫看到。
状态表示：使用四维状态（位置、步数、普通步数次数、闪现次数）进行BFS，确保每个状态唯一性。
剪枝条件：如果当前步数大于已知最优解步数，剪枝。
优先级处理：在找到多个解时，选择满足优先级条件的最优解。
import sysfrom collections import dequedef main(): n, m, c1, c2, d = map(int, sys.stdin.readline().split()) a = [[0]*(m+2) for _ in range(n+2)] realnot = [[False]*(m+2) for _ in range(n+2)] b = [[0]*(m+2) for _ in range(n+2)] sx, sy, tx, ty = 1,1,1,1 visited = [[[ [False]*(c2+1) for _ in range(c1+1)] for __ in range(n+2)] for ___ in range(m+2)] q = deque() q.append( (sx, sy, 0, 0, 0) ) visited[sx][sy][0][0] = True dirs = [ (-1,0), (1,0), (0,-1), (0,1) ] edirs = [ (-1,-1), (-1,1), (1,-1), (1,1) ] sdirs = [ (-d, 0), (d, 0), (0, -d), (0, d) ] while q: x, y, bc, hind, rush = q.popleft() if x == tx and y == ty: if ans == -1: ans = bc hind_count = hind rush_count = rush else: if bc < ans: ans = bc hind_count = hind rush_count = rush elif bc == ans: if hind + rush < hind_count + rush_count: hind_count = hind rush_count = rush elif hind + rush == hind_count + rush_count: if hind < hind_count: hind_count = hind rush_count = rush continue for dx, dy in dirs: nx = x + dx ny = y + dy if 1 <= nx <= n and 1 <= ny <= m: if a[nx][ny] == -1: if bin((nx, ny, bc+1, hind, rush)): q.append( (nx, ny, bc+1, hind, rush) ) elif hind < c1 and not realnot[nx][ny]: if bin((nx, ny, bc+1, hind+1, rush)): q.append( (nx, ny, bc+1, hind+1, rush) ) for dx, dy in edirs: nx = x + dx ny = y + dy if 1 <= nx <= n and 1 <= ny <= m: if a[nx][ny] == -1: if bin((nx, ny, bc+1, hind, rush)): q.append( (nx, ny, bc+1, hind, rush) ) elif hind < c1 and not realnot[nx][ny]: if bin((nx, ny, bc+1, hind+1, rush)): q.append( (nx, ny, bc+1, hind+1, rush) ) for dx, dy in sdirs: nx = x + dx ny = y + dy if 1 <= nx <= n and 1 <= ny <= m: if a[nx][ny] == -1: if bin((nx, ny, bc+1, hind, rush)): q.append( (nx, ny, bc+1, hind, rush) ) elif hind < c1 and not realnot[nx][ny]: if bin((nx, ny, bc+1, hind+1, rush)): q.append( (nx, ny, bc+1, hind+1, rush) ) if ans == -1: print(-1) else: print(f"{ans} {hind_count} {rush_count}")def bin(x): global visited if x[0] < 1 or x[0] > n or x[1] < 1 or x[1] > m: return False if visited[x[0]][x[1]][x[2]][x[3]]: return False visited[x[0]][x[1]][x[2]][x[3]] = True return Trueif __name__ == "__main__": main() 预处理护卫可见区域：使用差分方法计算每个点是否被护卫看到。
BFS初始化：从起点出发，初始化队列和访问数组。
处理普通走和闪现：在每一步中，分别处理普通走和闪现，检查是否可以使用，并更新相应的状态。
剪枝条件：如果当前步数大于已知最优解，剪枝。
优先级处理：在找到终点时，选择满足优先级条件的最优解。
通过以上步骤，我们可以高效地解决荆轲刺秦王问题，确保找到最优路径。
转载地址：http://iivh.baihongyu.com/