列表

详情

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

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [ri, ci] 表示第 i 个棋子现在在棋盘上的位置为 (ri, ci) ，棋盘下标从 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 个是有效的。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) { } };

cpp 解法, 执行用时: 80 ms, 内存消耗: 17.4 MB, 提交时间: 2023-09-24 23:18:12 

class Solution {
public:
    int countCombinations(vector<string>& pieces, vector<vector<int>>& pos) {
        int dx[] = {1,-1,0,0,1,-1,-1,1};
        int dy[] = {0,0,1,-1,1,-1,1,-1};

        for(int i = 0; i < pos.size(); ++i) --pos[i][0], --pos[i][1];
        
        pair<int,int> m[4];
        
        auto sim = [&]() -> int {
            int board[8][8];
            memset(board, 0, sizeof(board));
            pair<int,int> move[4]; // 这里如果是 vector 就会很慢，被卡常了
            int curpos[4][2];
            for(int i = 0; i < pos.size(); ++i) 
                move[i] = m[i], curpos[i][0] = pos[i][0], curpos[i][1] = pos[i][1];
            for(;;) {
                bool moved = false;
                for(int i = 0; i < pos.size(); ++i) {
                    if(move[i].second > 0) {
                        moved = true;
                        --move[i].second;
                        curpos[i][0] += dx[move[i].first];
                        curpos[i][1] += dy[move[i].first];
                    }
                }
                if(!moved) return 1;
                for(int i = 0; i < pos.size(); ++i) {
                    if(++board[curpos[i][0]][curpos[i][1]] > 1) return 0;
                }
                
                for(int i = 0; i < pos.size(); ++i) {
                    board[curpos[i][0]][curpos[i][1]] = 0;
                }
            }
        };
        
        int res = 0;

        function<void(int)> dfs = [&] (int i) {
            if(i == pieces.size()){ res += sim() ; return;}
            int mind, maxd;
            if(pieces[i][0] == 'r') mind = 0, maxd = 3;
            if(pieces[i][0] == 'q') mind = 0, maxd = 7;
            if(pieces[i][0] == 'b') mind = 4, maxd = 7;
            for(int d = mind; d <= maxd; ++d) {
                for(int l = 1; l <= 8; ++l) {
                    if(pos[i][0] + l * dx[d] >= 0 && pos[i][0] + l*dx[d] < 8 
                       && pos[i][1] + l*dy[d] >= 0 && pos[i][1] + l*dy[d] < 8) { // 剪枝限制移动步数
                        m[i].first = d, m[i].second = l;
                        dfs(i + 1);
                    }
                }
            }
            m[i].first = 0;
            m[i].second = 0;
            dfs(i + 1);
        };
        
        dfs(0);
        
        return res;
    }
};

python3 解法, 执行用时: 2100 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-24 23:17:45 

D = {"rook":    ((0, 1), (0, -1), (1, 0), (-1, 0)),
     "bishop":  ((1, 1), (1, -1), (-1, 1), (-1, -1)),
     "queen":   ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1))}
    
def get_moves(p, x, y):
    yield x, y, 0, 0, 0
    for t, (dx, dy) in product(range(1, 8), D[p]):
        if 1 <= x + dx * t <= 8 and 1 <= y + dy * t <= 8:
            yield x, y, dx, dy, t
            
def check(status) -> bool:
    for t in range(8):
        seen = set()
        for x, y, dx, dy, pt in status:
            dt = min(t, pt)
            if (px := x + dx * dt, py := y + dy * dt) in seen: return False
            seen.add((px, py))
    return True
    
class Solution:
    def countCombinations(self, P: List[str], POS: List[List[int]]) -> int:
        return sum(check(status) for status in product(*[get_moves(p, x, y) for p, (x, y) in zip(P, POS)]))

golang 解法, 执行用时: 8 ms, 内存消耗: 2.5 MB, 提交时间: 2023-09-24 23:17:09 

/**
 * 预处理每个棋子的所有合法移动，然后递归判断，对当前递归的棋子的合法移动，
 * 判断是否与前面的棋子的合法移动相冲突，若无冲突则往下递归。
 */
type move struct{ dx, dy, t int } // (dx,dy) 表示移动方向，t 表示移动的步数（时间）

func validMovesRook(x, y int) (m []move) {
	m = append(m, move{}) // 为了方便无重复地计算皇后
	for i := 1; i <= 8; i++ {
		if i != x {
			m = append(m, move{(i - x) / abs(i-x), 0, abs(i - x)})
		}
	}
	for j := 1; j <= 8; j++ {
		if j != y {
			m = append(m, move{0, (j - y) / abs(j-y), abs(j - y)})
		}
	}
	return
}

func validMovesBishop(x, y int) (m []move) {
	m = append(m, move{}) // 为了方便无重复地计算皇后
	for i := 1; i <= 8; i++ {
		for j := 1; j <= 8; j++ {
			if (i != x || j != y) && abs(i-x) == abs(j-y) {
				m = append(m, move{(i - x) / abs(i-x), (j - y) / abs(j-y), abs(i - x)})
			}
		}
	}
	return
}

func validMovesQueen(x, y int) []move { // 皇后可以有上面两种移动方式
	return append(append([]move{{}}, validMovesRook(x, y)[1:]...), validMovesBishop(x, y)[1:]...)
}

// 判断是否合法，即不存在两个棋子占据同一个格子的情况
func isValid(x1, y1, x2, y2 int, m1, m2 move) bool {
	for i := 1; i <= m1.t || i <= m2.t; i++ {
		if i <= m1.t {
			x1 += m1.dx // 每一秒走一步
			y1 += m1.dy
		}
		if i <= m2.t {
			x2 += m2.dx
			y2 += m2.dy
		}
		if x1 == x2 && y1 == y2 { // 两个棋子占据了同一个格子
			return false
		}
	}
	return true
}

func countCombinations(pieces []string, positions [][]int) (ans int) {
	n := len(pieces)
	validMoves := make([][]move, n)
	for i, p := range positions {
		x, y := p[0], p[1]
		if pieces[i] == "rook" {
			validMoves[i] = validMovesRook(x, y) // 预处理所有合法移动
		} else if pieces[i] == "bishop" {
			validMoves[i] = validMovesBishop(x, y)
		} else {
			validMoves[i] = validMovesQueen(x, y)
		}
	}

	moves := make([]move, n)
	var f func(int)
	f = func(i int) {
		if i == n {
			ans++
			return
		}
		x1, y1 := positions[i][0], positions[i][1]
	outer:
		for _, m := range validMoves[i] { // 枚举当前棋子的所有合法移动
			for j, pos := range positions[:i] { // 枚举前面的棋子的移动
				if !isValid(x1, y1, pos[0], pos[1], m, moves[j]) { // 判断该移动是否与前面的棋子的移动相冲突
					continue outer
				}
			}
			moves[i] = m // 无冲突
			f(i + 1) // 递归进入下一个棋子
		}
	}
	f(0)
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

上一题

© 2024 leetcode.cn