棋盘上有效移动组合的数目

难度: Hard

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [r_i, c_i] 表示第 i 个棋子现在在棋盘上的位置为 (r_i, c_i) ，棋盘下标从 1 开始。

棋盘上每个棋子都可以移动 至多一次 。每个棋子的移动中，首先选择移动的方向，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：

车可以 水平或者竖直 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1) 或者 (r, c-1) 移动。
后可以 水平竖直或者斜对角 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1)，(r, c-1)，(r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
象可以 斜对角 从 (r, c) 沿着方向 (r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。

移动组合 包含所有棋子的移动。每一秒，每个棋子都沿着它们选择的方向往前移动一步，直到它们到达目标位置。所有棋子从时刻 0 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效 。

请你返回有效移动组合的数目。

注意：

初始时，不会有两个棋子 在 同一个位置。
有可能在一个移动组合中，有棋子不移动。
如果两个棋子 直接相邻 且两个棋子下一秒要互相占据对方的位置，可以将它们在同一秒内 交换位置 。

示例 1:

输入：pieces = ["rook"], positions = [[1,1]]
输出：15
解释：上图展示了棋子所有可能的移动。

示例 2：

输入：pieces = ["queen"], positions = [[1,1]]
输出：22
解释：上图展示了棋子所有可能的移动。

示例 3:

输入：pieces = ["bishop"], positions = [[4,3]]
输出：12
解释：上图展示了棋子所有可能的移动。

示例 4:

输入：pieces = ["rook","rook"], positions = [[1,1],[8,8]]
输出：223
解释：每个车有 15 种移动，所以总共有 15 * 15 = 225 种移动组合。
但是，有两个是不有效的移动组合：
- 将两个车都移动到 (8, 1) ，会导致它们在同一个格子相遇。
- 将两个车都移动到 (1, 8) ，会导致它们在同一个格子相遇。
所以，总共有 225 - 2 = 223 种有效移动组合。
注意，有两种有效的移动组合，分别是一个车在 (1, 8) ，另一个车在 (8, 1) 。
即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。

示例 5：

输入：pieces = ["queen","bishop"], positions = [[5,7],[3,4]]
输出：281
解释：总共有 12 * 24 = 288 种移动组合。
但是，有一些不有效的移动组合：
- 如果后停在 (6, 7) ，它会阻挡象到达 (6, 7) 或者 (7, 8) 。
- 如果后停在 (5, 6) ，它会阻挡象到达 (5, 6) ，(6, 7) 或者 (7, 8) 。
- 如果象停在 (5, 2) ，它会阻挡后到达 (5, 2) 或者 (5, 1) 。
在 288 个移动组合当中，281 个是有效的。

提示：

n == pieces.length
n == positions.length
1 <= n <= 4
pieces 只包含字符串 "rook" ，"queen" 和 "bishop" 。
棋盘上总共最多只有一个后。
1 <= x_i, y_i <= 8
每一个 positions[i] 互不相同。

Submission

运行时间: 300 ms

内存: 16.9 MB

class Solution:
    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
        def f(x: int, y: int) -> int:
            return x * 9 + y

        n = len(pieces)
        a = [[] for _ in range(n)]
        line = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        diag = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
        for i, role in enumerate(pieces):
            x, y = positions[i]
            a[i].append([f(x, y)])
            d = []
            if role == 'rook' or role == 'queen':
                d.extend(line)
            if role == 'bishop' or role == 'queen':
                d.extend(diag)
            for dx, dy in d:
                path = [(x, y)]
                cx, cy = x + dx, y + dy
                while cx > 0 and cx < 9 and cy > 0 and cy < 9:
                    path.append(f(cx, cy))
                    a[i].append(path.copy())
                    cx += dx
                    cy += dy
        indexes = [0] * n

        def validate(path1: List[int], path2: List[int]) -> bool:
            if len(path1) < len(path2):
                path1, path2 = path2, path1
            n1, n2 = len(path1), len(path2)
            for i in range(n2):
                if path1[i] == path2[i]:
                    return False
            for i in range(n2, n1):
                if path1[i] == path2[n2-1]:
                    return False
            return True

        def dfs(level: int) -> int:
            if level == n:
                return 1
            res = 0
            m = len(a[level])
            for i in range(m):
                indexes[level] = i
                valid = True
                for p in range(level):
                    if not validate(a[p][indexes[p]], a[level][i]):
                        valid = False
                        break
                if valid:
                    res += dfs(level + 1)
            return res

        return dfs(0)

Explain

这个解决方案使用了深度优先搜索 (DFS) 来遍历所有可能的棋子移动组合，并验证每个组合的有效性。每种棋子（车、后、象）可以沿不同的方向移动到棋盘的不同位置。对每个棋子，算法首先计算出所有可能的单次移动路径。然后，使用DFS尝试所有可能的移动组合，同时利用一个验证函数来确保没有两个棋子在同一时间占据同一个位置或者互换位置。验证函数比较两个路径的每个步骤，检查是否存在冲突。最终，算法返回所有有效组合的数量。

时间复杂度: O(M^n * n^2)

空间复杂度: O(n * M)

class Solution:
    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
        def f(x: int, y: int) -> int:
            # 将棋盘坐标转换为一个唯一的数值标识
            return x * 9 + y

        n = len(pieces)
        a = [[] for _ in range(n)] # 存储每个棋子的所有可能的移动路径
        line = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 车和后的直线移动方向
        diag = [(-1, -1), (-1, 1), (1, -1), (1, 1)] # 后和象的对角线移动方向
        for i, role in enumerate(pieces):
            x, y = positions[i]
            a[i].append([f(x, y)]) # 包括原地不动的情况
            d = []
            if role == 'rook' or role == 'queen':
                d.extend(line)
            if role == 'bishop' or role == 'queen':
                d.extend(diag)
            for dx, dy in d:
                path = [(x, y)]
                cx, cy = x + dx, y + dy
                while cx > 0 and cx < 9 and cy > 0 and cy < 9:
                    path.append(f(cx, cy)) # 记录从起始点到终点的完整路径
                    a[i].append(path.copy())
                    cx += dx
                    cy += dy
        indexes = [0] * n # 记录每个棋子当前选择的路径索引

        def validate(path1: List[int], path2: List[int]) -> bool:
            # 验证两条路径是否有冲突
            if len(path1) < len(path2):
                path1, path2 = path2, path1
            n1, n2 = len(path1), len(path2)
            for i in range(n2):
                if path1[i] == path2[i]:
                    return False
            for i in range(n2, n1):
                if path1[i] == path2[n2-1]:
                    return False
            return True

        def dfs(level: int) -> int:
            # 递归函数来尝试所有可能的移动组合
            if level == n:
                return 1
            res = 0
            m = len(a[level])
            for i in range(m):
                indexes[level] = i
                valid = True
                for p in range(level):
                    if not validate(a[p][indexes[p]], a[level][i]):
                        valid = False
                        break
                if valid:
                    res += dfs(level + 1)
            return res

        return dfs(0)

Explore

函数`f(x: int, y: int) -> int`通过将二维棋盘坐标转换为一个唯一的一维数值，简化了棋子位置的比较和存储过程。这种转换允许算法使用简单的整数比较来检查位置冲突，而不是比较一个包含两个整数的列表或元组。这样可以减少内存占用，并且能够在验证函数中更加高效地比较位置，从而提高了算法的性能。

记录从起始点到每个可能终点的完整路径是为了在验证函数中检查路径上的任何位置是否与其他棋子的路径冲突。如果只存储终点位置，我们无法确定移动过程中是否有位置重叠，这对于确保每一步移动的有效性是不够的。通过存储完整路径，可以确保在棋盘上的任何时刻，棋子都不会出现在同一位置。

在递归函数`dfs`中，算法尝试为每个棋子选择一条移动路径，并使用`validate`函数检查当前选择的路径是否与之前选择的路径有冲突。`validate`函数通过比较两条路径上对应的位置来执行这一检查。如果在任何时间点，两条路径上的位置相同（即棋子占据同一位置），则认为存在冲突。此外，如果在较短路径结束后，较长路径仍然经过较短路径的最后一个位置，则也会认为存在冲突，这防止了棋子在移动结束时的位置重叠。

是的，算法考虑了棋子移动可能导致的重叠情况。这通过在每次尝试棋子移动路径时使用`validate`函数来处理。该函数确保所有棋子的移动路径在任何时刻都不会导致位置重叠。如果检测到冲突，当前路径组合被丢弃，算法继续尝试其他路径组合。这样确保了所有在算法最终输出中计算的移动组合都是有效的，没有棋子重叠的情况。