广东二次疫情最新消息_安徽省建设工程信息网怎么打不开了_郑州seo外包平台_河北seo网络推广

题目描述：

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [ri, ci] 表示第 i 个棋子现在在棋盘上的位置为 (ri, ci) ，棋盘下标从 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. 初始化变量：
   • ans 用于存储所有合法的摆放方式的数量。
   • n 是棋子的数量。
   • 将 positions 数组中的每个棋子的起始位置坐标减去1，这是因为棋盘坐标通常从(0,0)开始，而题目可能给出的坐标是从(1,1)开始的。
2. 定义方向和可能的移动：
   • d 是一个字典，用于存储每个方向（0-8）对应的坐标变化。这些方向分别对应：右(0,1)、上(1,0)、左(0,-1)、下(-1,0)、右上(1,1)、右下(1,-1)、左上(-1,1)、左下(-1,-1)。
   • can 是一个字典，用于存储每种棋子（车、后、象）可以移动的方向。车(rook)只能直行或横行，后(queen)可以直行、横行和斜行，象(bishop)只能斜行。
3. 深度优先搜索（DFS）：
   • dfs 函数用于递归地尝试放置每个棋子，并检查当前放置是否合法。
   • 递归的终止条件是当所有棋子都放置完毕（i == n）。
   • 在递归的每一步，首先检查当前放置是否会导致棋子重合（即两个棋子在同一位置）。这是通过检查每个棋子在其所有可能的移动路径上是否有其他棋子占据同一位置来实现的。
   • 对于每个棋子，根据其类型（车、后、象），尝试所有可能的合法移动。对于车和后，考虑从1到7步的移动；对于象，由于它只能斜着走，只要路径在棋盘内，就可以继续尝试。
   • 如果当前放置是合法的（即没有棋子重合），则更新 ans 的值。
4. 执行DFS：
   • 从第一个棋子开始，调用 dfs 函数进行递归搜索。
5. 返回结果：
   • 返回所有合法的摆放方式的数量 ans。

总结来说，这个代码通过深度优先搜索（DFS）来遍历所有可能的棋子摆放方式，并使用字典和集合来高效地检查棋子的重合情况和可能的移动路径。通过递归地放置每个棋子，并检查每一步的合法性，最终计算出所有合法的摆放方式的数量。

代码实现： 

class Solution:def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:ans = 0n = len(pieces)for i in range(n):positions[i][0] -= 1positions[i][1] -= 1d = {0:(0,0),1:(0,1),2:(1,0),3:(0,-1),4:(-1,0),5:(1,1),6:(1,-1),7:(-1,1),8:(-1,-1)}can = {'rook':[0,1,2,3,4],'queen':[0,1,2,3,4,5,6,7,8],'bishop':[0,5,6,7,8]}ans = 0def dfs(i,cur):nonlocal ans# 检查每一步是否存在棋子重合if i == n:mx = max(v[0] for v in cur)f = 1for j in range(1,mx + 1):v = set()for k in range(n):cv,cd = cur[k]if cv < j:nx,ny = positions[k][0] + cv * d[cd][0],positions[k][1] + cv * d[cd][1]if (nx,ny) in v:f = 0breakv.add((nx,ny))else:nx,ny = positions[k][0] + j * d[cd][0],positions[k][1] + j * d[cd][1]if (nx,ny) in v:f = 0breakv.add((nx,ny))if not f:breakif f:ans += 1returndir_ = can[pieces[i]]x,y = positions[i]k = len(dir_)# 生成当前棋子所有的可能移动方式for j in range(k):if dir_[j] == 0:dfs(i + 1,cur + [[0,0]])else:for ii in range(1,8):nx,ny = x + ii * d[dir_[j]][0],y + ii * d[dir_[j]][1]if nx < 0 or ny < 0 or nx >= 8 or ny >= 8:breakdfs(i + 1,cur + [[ii,dir_[j]]])returndfs(0,[])return ans