wordpress 去掉头部,网站建设优化服务熊掌号,嵌入式开发板,领地网做网站咋加文章Leetcode 3283. Maximum Number of Moves to Kill All Pawns 1. 解题思路2. 代码实现 题目链接#xff1a;3283. Maximum Number of Moves to Kill All Pawns
1. 解题思路
这一题坦率地说没有想到什么好的思路#xff0c;因此只能非常暴力地按照题意进行了一下构造。
显然…Leetcode 3283. Maximum Number of Moves to Kill All Pawns 1. 解题思路2. 代码实现 题目链接3283. Maximum Number of Moves to Kill All Pawns
1. 解题思路
这一题坦率地说没有想到什么好的思路因此只能非常暴力地按照题意进行了一下构造。
显然这个题目可以拆分为两个小题目
给出任意 50 × 50 50\times50 50×50的棋盘上的两个点A和B求令马从点A跳到点B所需的最小步数。Alice和Bob的吃兵游戏。
其中前者本应有一些比较漂亮的解答的这里我倒是没有想到啥好的最后就是暴力的走了一个宽度优先的遍历。
而关于第二小题我们的解法则更加暴力就是分别构造了两个耦合的动态规划算法来翻译了一下题目的过程其伪代码如下
def dp_alice(position, status):if status 2**n-1:return 0return max(step(position, points[i]) dp_bob(points[i], status | (1 i)) for i in range(n) if status (1 i) 0)def dp_bob(position, status):if status 2**n-1:return 0return min(step(position, points[i]) dp_alice(points[i], status | (1 i)) for i in range(n) if status (1 i) 0)这里我们用一个整数的二进制上的位来记录每一个坐标位置 i i i上的兵是否已经被吃掉了。
2. 代码实现
给出最终的python代码实现如下
lru_cache(None)
def move(x0, y0, x1, y1):dirs [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]if abs(x0-x1) 2 * abs(y0-y1):return abs(y0-y1)if abs(y0-y1) 2 * abs(x0-x1):return abs(x0-x1)q [(0, abs(x0-x1) abs(y0-y1), x0, y0)]seen {(x0, y0)}while q:step, _, x, y heapq.heappop(q)for dx, dy in dirs:if x dx x1 and ydy y1:return step1if 0 xdx 50 and 0 ydy 50 and (xdx, ydy) not in seen:seen.add((xdx, ydy))heapq.heappush(q, (step1, abs(xdx-x1) abs(ydy-y1), xdx, ydy))return math.infclass Solution:def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) - int:n len(positions)END 2**n-1lru_cache(None)def dp_alice(x, y, status):if status END:return 0ans 0for i in range(n):if status (1 i) ! 0:continuex1, y1 positions[i][0], positions[i][1]ans max(ans, move(x, y, x1, y1) dp_bob(x1, y1, status | (1 i)))return anslru_cache(None)def dp_bob(x, y, status):if status END:return 0ans math.inffor i in range(n):if status (1 i) ! 0:continuex1, y1 positions[i][0], positions[i][1]ans min(ans, move(x, y, x1, y1) dp_alice(x1, y1, status | (1 i)))return ansreturn dp_alice(kx, ky, 0)提交代码评测得到耗时11035ms占用内存119MB。
