Hard

题目描述

在一个 50 x 50 的棋盘上有一个骑士和一些兵。给定两个整数 kx 和 ky，其中 (kx, ky) 表示骑士的位置，还有一个二维数组 positions，其中 positions[i] = [xi, yi] 表示棋盘上兵的位置。

Alice 和 Bob 进行回合制游戏，Alice 先手。在每个玩家的回合中：

  • 玩家选择一个仍存在于棋盘上的兵，并用骑士以最少的移动次数捕获它。注意玩家可以选择任何兵，不一定是能够以最少移动次数捕获的兵。
  • 在捕获选定兵的过程中，骑士可能经过其他兵而不捕获它们。在这个回合中只能捕获选定的兵。

Alice 试图最大化两个玩家在棋盘上没有更多兵之前所做的移动次数总和，而 Bob 试图最小化它们。

返回 Alice 在两个玩家都发挥最优的情况下能够实现的最大总移动次数。

注意在一次移动中，象棋骑士有八个可能的位置可以移动，如下所示。每次移动都是在基本方向上移动两个格子，然后在正交方向上移动一个格子。

示例 1：

输入：kx = 1, ky = 1, positions = [[0,0]]
输出：4
解释：骑士需要 4 步到达 (0, 0) 处的兵。

示例 2：

输入：kx = 0, ky = 2, positions = [[1,1],[2,2],[3,3]]
输出：8
解释：
- Alice 选择 (2, 2) 处的兵，用两步捕获：(0, 2) -> (1, 4) -> (2, 2)
- Bob 选择 (3, 3) 处的兵，用两步捕获：(2, 2) -> (4, 1) -> (3, 3)
- Alice 选择 (1, 1) 处的兵，用四步捕获：(3, 3) -> (4, 1) -> (2, 2) -> (0, 3) -> (1, 1)

示例 3：

输入：kx = 0, ky = 0, positions = [[1,2],[2,4]]
输出：3
解释：
- Alice 选择 (2, 4) 处的兵，用两步捕获：(0, 0) -> (1, 2) -> (2, 4)
- Bob 选择 (1, 2) 处的兵，用一步捕获：(2, 4) -> (1, 2)

约束条件：

  • 0 <= kx, ky <= 49
  • 1 <= positions.length <= 15
  • positions[i].length == 2
  • 0 <= positions[i][0], positions[i][1] <= 49
  • 所有 positions[i] 都是唯一的
  • 对于所有 0 <= i < positions.length，positions[i] != [kx, ky]

解题思路

这是一个博弈论问题，需要使用动态规划和位掩码来解决。

核心思路：

  1. 预处理距离：使用BFS计算从每个位置（包括骑士初始位置）到每个兵的最短距离
  2. 博弈DP：使用位掩码表示已被捕获的兵的状态，用DP来模拟最优博弈
  3. Minimax策略：Alice试图最大化总移动次数，Bob试图最小化

详细步骤：

  • 首先将骑士初始位置也当作一个"位置"，这样便于统一处理
  • 对每个位置使用BFS计算到所有兵的最短距离
  • 使用dp[mask][pos]表示在状态mask下（mask表示哪些兵已被捕获），当前位置为pos时的最优结果
  • Alice回合时选择能使总移动数最大的兵，Bob回合时选择能使总移动数最小的兵
  • 状态转移时枚举下一个要捕获的兵，累加对应的移动距离

位掩码技巧：

  • 使用整数的二进制位表示兵的捕获状态
  • mask & (1 << i)检查第i个兵是否已被捕获
  • mask | (1 << i)表示捕获第i个兵后的状态

时间复杂度主要由状态数决定：O(n * 2^n * 50^2)，其中BFS预处理和DP状态转移都需要考虑。

代码实现

class Solution {
public:
    int maxMoves(int kx, int ky, vector<vector<int>>& positions) {
        int n = positions.size();
        // 将骑士位置加入positions数组的开头
        positions.insert(positions.begin(), {kx, ky});
        
        // BFS计算任意两点间的最短距离
        vector<vector<int>> dist(n + 1, vector<int>(n + 1));
        int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
        int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
        
        for (int i = 0; i <= n; i++) {
            vector<vector<int>> d(50, vector<int>(50, -1));
            queue<pair<int, int>> q;
            q.push({positions[i][0], positions[i][1]});
            d[positions[i][0]][positions[i][1]] = 0;
            
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                
                for (int k = 0; k < 8; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    
                    if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.push({nx, ny});
                    }
                }
            }
            
            for (int j = 0; j <= n; j++) {
                dist[i][j] = d[positions[j][0]][positions[j][1]];
            }
        }
        
        // DP: dp[mask][pos] 表示在状态mask下，当前在pos位置的最优值
        vector<vector<int>> dp(1 << n, vector<int>(n + 1, -1));
        
        function<int(int, int, bool)> dfs = [&](int mask, int pos, bool isAlice) -> int {
            if (mask == (1 << n) - 1) return 0; // 所有兵都被捕获
            
            if (dp[mask][pos] != -1) return dp[mask][pos];
            
            int result = isAlice ? 0 : INT_MAX;
            
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue; // 第i个兵已被捕获
                
                int newMask = mask | (1 << i);
                int cost = dist[pos][i + 1]; // +1因为positions[0]是骑士位置
                int subResult = dfs(newMask, i + 1, !isAlice);
                
                if (isAlice) {
                    result = max(result, cost + subResult);
                } else {
                    result = min(result, cost + subResult);
                }
            }
            
            return dp[mask][pos] = result;
        };
        
        return dfs(0, 0, true);
    }
};

class Solution:
    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
        from collections import deque
        
        n = len(positions)
        # 将骑士位置加入positions数组的开头
        positions = [[kx, ky]] + positions
        
        # BFS计算任意两点间的最短距离
        dist = [[0] * (n + 1) for _ in range(n + 1)]
        dx = [-2, -2, -1, -1, 1, 1, 2, 2]
        dy = [-1, 1, -2, 2, -2, 2, -1, 1]
        
        for i in range(n + 1):
            d = [[-1] * 50 for _ in range(50)]
            queue = deque([(positions[i][0], positions[i][1])])
            d[positions[i][0]][positions[i][1]] = 0
            
            while queue:
                x, y = queue.popleft()
                
                for k in range(8):
                    nx, ny = x + dx[k], y + dy[k]
                    
                    if 0 <= nx < 50 and 0 <= ny < 50 and d[nx][ny] == -1:
                        d[nx][ny] = d[x][y] + 1
                        queue.append((nx, ny))
            
            for j in range(n + 1):
                dist[i][j] = d[positions[j][0]][positions[j][1]]
        
        # DP with memoization
        dp = {}
        
        def dfs(mask, pos, is_alice):
            if mask == (1 << n) - 1:  # 所有兵都被捕获
                return 0
            
            if (mask, pos, is_alice) in dp:
                return dp[(mask, pos, is_alice)]
            
            result = 0 if is_alice else float('inf')
            
            for i in range(n):
                if mask & (1 << i):  # 第i个兵已被捕获
                    continue
                
                new_mask = mask | (1 << i)
                cost = dist[pos][i + 1]  # +1因为positions[0]是骑士位置
                sub_result = dfs(new_mask, i + 1, not is_alice)
                
                if is_alice:
                    result = max(result, cost + sub_result)
                else:
                    result = min(result, cost + sub_result)
            
            dp[(mask, pos, is_alice)] = result
            return result
        
        return dfs(0, 0, True)

public class Solution {
    public int MaxMoves(int kx, int ky, int[][] positions) {
        int n = positions.Length;
        // 将骑士位置加入positions数组的开头
        int[][] allPositions = new int[n + 1][];
        allPositions[0] = new int[] {kx, ky};
        for (int i = 0; i < n; i++) {
            allPositions[i + 1] = positions[i];
        }
        
        // BFS计算任意两点间的最短距离
        int[,] dist = new int[n + 1, n + 1];
        int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
        
        for (int i = 0; i <= n; i++) {
            int[,] d = new int[50, 50];
            for (int x = 0; x < 50; x++) {
                for (int y = 0; y < 50; y++) {
                    d[x, y] = -1;
                }
            }
            
            Queue<(int, int)> queue = new Queue<(int, int)>();
            queue.Enqueue((allPositions[i][0], allPositions[i][1]));
            d[allPositions[i][0], allPositions[i][1]] = 0;
            
            while (queue.Count > 0) {
                var (x, y) = queue.Dequeue();
                
                for (int k = 0; k < 8; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    
                    if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && d[nx, ny] == -1) {
                        d[nx, ny] = d[x, y] + 1;
                        queue.Enqueue((nx, ny));
                    }
                }
            }
            
            for (int j = 0; j <= n; j++) {
                dist[i, j] = d[allPositions[j][0], allPositions[j][1]];
            }
        }
        
        // DP with memoization
        Dictionary<(int, int, bool), int> memo = new Dictionary<(int, int, bool), int>();
        
        int Dfs(int mask, int pos, bool isAlice) {
            if (mask == (1 << n) - 1) return 0; // 所有兵都被捕获
            
            if (memo.ContainsKey((mask, pos, isAlice))) {
                return memo[(mask, pos, isAlice)];
            }
            
            int result = isAlice ? 0 : int.MaxValue;
            
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue; // 第i个兵已被捕获
                
                int newMask = mask | (1 << i);
                int cost = dist[pos, i + 1]; // +1因为allPositions[0]是骑士位置
                int subResult = Dfs(newMask, i + 1, !isAlice);
                
                if (isAlice) {
                    result = Math.Max(result, cost + subResult);
                } else {
                    result = Math.Min(result, cost + subResult);
                }
            }
            
            memo[(mask, pos, isAlice)] = result;
            return result;
        }
        
        return Dfs(0, 0, true);
    }
}

var maxMoves = function(kx, ky, positions) {
    const n = positions.length;
    const moves = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]];
    
    // Calculate shortest distance between any two positions using BFS
    function bfs(startX, startY, endX, endY) {
        if (startX === endX && startY === endY) return 0;
        
        const queue = [[startX, startY, 0]];
        const visited = new Set();
        visited.add(`${startX},${startY}`);
        
        while (queue.length > 0) {
            const [x, y, dist] = queue.shift();
            
            for (const [dx, dy] of moves) {
                const nx = x + dx;
                const ny = y + dy;
                const key = `${nx},${ny}`;
                
                if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50 && !visited.has(key)) {
                    if (nx === endX && ny === endY) return dist + 1;
                    visited.add(key);
                    queue.push([nx, ny, dist + 1]);
                }
            }
        }
        return Infinity;
    }
    
    // Precompute distances from knight position to all pawns and between all pairs of pawns
    const dist = Array(n + 1).fill(null).map(() => Array(n + 1).fill(0));
    
    // Distance from knight to each pawn
    for (let i = 0; i < n; i++) {
        dist[n][i] = bfs(kx, ky, positions[i][0], positions[i][1]);
    }
    
    // Distance between each pair of pawns
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j) {
                dist[i][j] = bfs(positions[i][0], positions[i][1], positions[j][0], positions[j][1]);
            }
        }
    }
    
    // DP with memoization
    const memo = new Map();
    
    function dp(mask, lastPos, isAlice) {
        const key = `${mask},${lastPos},${isAlice}`;
        if (memo.has(key)) return memo.get(key);
        
        if (mask === (1 << n) - 1) return 0;
        
        let result = isAlice ? -Infinity : Infinity;
        
        for (let i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                const newMask = mask | (1 << i);
                const moveCost = lastPos === n ? dist[n][i] : dist[lastPos][i];
                const totalCost = moveCost + dp(newMask, i, !isAlice);
                
                if (isAlice) {
                    result = Math.max(result, totalCost);
                } else {
                    result = Math.min(result, totalCost);
                }
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, n, true);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目