05 August 2008
棋盘上有效移动组合的数目
有一个 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 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效 。
请返回 有效 移动组合的数目。
注意：
初始时，不会有两个棋子 在 同一个位置 。 有可能在一个移动组合中，有棋子不移动。 如果两个棋子 直接相邻 且两个棋子下一秒要互相占据对方的位置，可以将它们在同一秒内 交换位置 。
看到这种题意比较长的题目首先需要理顺题意，然后理顺思路，写起代码就简单了。
题意：
棋盘上有 3 种棋子，车，后，象。车只走 直线；后 直线、斜线 都走；象 只走 斜线。
我们需要选择 移动方案，在这个方案中：
首先，对每个棋子，指定 移动方向 和 步数。（棋子也可以不移动，此时移动方向已无意义，算做一种方案）
然后，每秒钟，每个棋子都会同时沿着 指定的方向 前进一步，直到步数耗尽。 如果某一 整数 时刻，有棋子 重叠，或者棋子 移出了界外，则为 无效方案；否则为有效方案。 返回有效方案的个数。
思路：
直接按题意模拟即可。首先枚举移动方案，然后再模拟移动的过程，检查是否为有效方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public int countCombinations(String[] pieces, int[][] positions) {
List<List<int[]>> allTargets = IntStream.range(0, pieces.length).mapToObj(i -> new ArrayList<int[]>()).collect(Collectors.toList());
for (int i = 0; i < pieces.length; i++) {
int[] pos = positions[i];
int x = pos[0];
int y = pos[1];
allTargets.get(i).add(pos);//add init position as a target
for (int row = 1; row <= 8; row++)
for (int col = 1; col <= 8; col++)
if (row != x || col != y) {//all but not init position, it is already added
if (!pieces[i].equals("rook") && (row + col == x + y || row - col == x - y)) {//valid target for bishop and queen
allTargets.get(i).add(new int[]{row, col});
}
if (!pieces[i].equals("bishop") && (row == x || col == y)) {//valid target for rook and queen
allTargets.get(i).add(new int[]{row, col});
}
}
}
return count(0, positions, allTargets, new LinkedList<>());
}
int count(int idx, int[][] initPositions, List<List<int[]>> allTargets, LinkedList<int[]> targets) {
if (idx == initPositions.length)
return valid(initPositions, targets) ? 1 : 0;
int count = 0;
for (int[] position : allTargets.get(idx)) {
targets.add(position);
count += count(idx + 1, initPositions, allTargets, targets);
targets.removeLast();
}
return count;
}
boolean valid(int[][] initPositions, List<int[]> targets) {
List<int[]> positions = Arrays.stream(initPositions).map(int[]::clone).collect(Collectors.toList());//deep copy init positions as we are going to move towards targets
for (boolean keepMoving = true; keepMoving; ) {
keepMoving = false;
Set<Integer> used = new HashSet<>();
for (int i = 0; i < positions.size(); i++) {
int verticalDirection = targets.get(i)[0] - positions.get(i)[0], horizontalDirection = targets.get(i)[1] - positions.get(i)[1];
positions.get(i)[0] += Integer.compare(verticalDirection, 0);
positions.get(i)[1] += Integer.compare(horizontalDirection, 0);
if (verticalDirection != 0 || horizontalDirection != 0) {//target is not reached
keepMoving = true;
}
if (!used.add(13 * positions.get(i)[0] + positions.get(i)[1])) {//collision with another piece
return false;
}
}
}
return true;
}
}