Leetcode 3283. Maximum Number of Moves to Kill All Pawns

• Leetcode 3283. Maximum Number of Moves to Kill All Pawns
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3283. Maximum Number of Moves to Kill All Pawns

1. 解题思路

这一题坦率地说没有想到什么好的思路，因此只能非常暴力地按照题意进行了一下构造。

显然，这个题目可以拆分为两个小题目：

1. 给出任意$50\times 50$的棋盘上的两个点A和B，求令马从点A跳到点B所需的最小步数。
2. 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$上的兵是否已经被吃掉了。

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 y+dy == y1:return step+1if 0 <= x+dx < 50 and 0 <= y+dy < 50 and (x+dx, y+dy) not in seen:seen.add((x+dx, y+dy))heapq.heappush(q, (step+1, abs(x+dx-x1) + abs(y+dy-y1), x+dx, y+dy))return math.infclass Solution:def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:n = len(positions)END = 2**n-1@lru_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 ans@lru_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。