【Leetcode 每日一题】2056. 棋盘上有效移动组合的数目

问题背景

有一个 8 × 8 8 \times 8 8×8 的棋盘，它包含 n n n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n n n 的字符串数组 p i e c e s pieces pieces，其中 p i e c e s [ i ] pieces[i] pieces[i] 表示第 i i i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n n n 的二维整数数组 p o s i t i o n s positions positions，其中 p o s i t i o n s [ i ] = [ r i , c i ] positions[i] = [r_i, c_i] positions[i]=[ri​,ci​] 表示第 i i i 个棋子现在在棋盘上的位置为 ( r i , c i ) (r_i, c_i) (ri​,ci​)，棋盘下标从 1 1 1 开始。
棋盘上每个棋子都可以移动 至多一次 。每个棋子的移动中，首先选择移动的 方向 ，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：

• 车可以 水平或者竖直 从 ( r , c ) (r, c) (r,c) 沿着方向 ( r + 1 , c ) (r + 1, c) (r+1,c)， ( r − 1 , c ) (r - 1, c) (r−1,c)， ( r , c + 1 ) (r, c + 1) (r,c+1)， ( r , c − 1 ) (r, c-1) (r,c−1)移动。
• 后可以 水平竖直或者斜对角 从 ( r , c ) (r, c) (r,c) 沿着方向 ( r + 1 , c ) (r + 1, c) (r+1,c)， ( r − 1 , c ) (r - 1, c) (r−1,c)， ( r , c + 1 ) (r, c + 1) (r,c+1)， ( r , c − 1 ) (r, c - 1) (r,c−1)， ( r + 1 , c + 1 ) (r + 1, c + 1) (r+1,c+1)， ( r + 1 , c − 1 ) (r + 1, c - 1) (r+1,c−1)， ( r − 1 , c + 1 ) (r - 1, c + 1) (r−1,c+1)， ( r − 1 , c − 1 ) (r - 1, c - 1) (r−1,c−1) 移动。
• 象可以 斜对角 从 ( r , c ) (r, c) (r,c) 沿着方向 ( r + 1 , c + 1 ) (r + 1, c + 1) (r+1,c+1)， ( r + 1 , c − 1 ) (r + 1, c - 1) (r+1,c−1)， ( r − 1 , c + 1 ) (r - 1, c + 1) (r−1,c+1)， ( r − 1 , c − 1 ) (r - 1, c - 1) (r−1,c−1) 移动。
  移动组合 包含所有棋子的 移动 。每一秒，每个棋子都沿着它们选择的方向往前移动 一步 ，直到它们到达目标位置。所有棋子从时刻 0 0 0开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 无效 。
  请你返回 有效 移动组合的数目。

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

数据约束

• n = p i e c e s . l e n g t h n = pieces.length n=pieces.length
• n = p o s i t i o n s . l e n g t h n = positions.length n=positions.length
• 1 ≤ n ≤ 4 1 \le n \le 4 1≤n≤4
• p i e c e s pieces pieces 只包含字符串 “rook” ，“queen” 和 “bishop” 。
• 棋盘上最多只有一个后。
• 1 ≤ r i , c i ≤ 8 1 \le r_i, c_i \le 8 1≤ri​,ci​≤8
• 每一个 p o s i t i o n s [ i ] positions[i] positions[i] 互不相同

解题过程

很遗憾没有做出来，抄完 灵神的题解 回过头来看这题在算法考察这方面并不是特别难。所有的棋子都是同时移动，数据量不是很大，并且限制比较多，这当然也是能用回溯的前提。
回溯的思路是比较简单的，每一层确定一个棋子的位置，根据它移动的情况去挨个判断会不会跟之前已经存在的棋子重叠，不累计重叠的情况。

但是除了核心点以外的处理，还是有些复杂的。
尤其是定义一个类来刻画移动的情形目前我是完全没想到，见世面了算是。

具体实现

class Solution {

    // 常量定义，SIZE 表示棋子下标的上界，PIECE_DIRECITONS 表示不同棋子可能的移动方向
    private static final int SIZE = 8;
    private static final Map<Character, int[][]> PIECE_DIRECTIONS = Map.of(
        'r', new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}},
        'b', new int[][]{{1, 1}, {-1, 1}, {-1, -1}, {1, -1}},
        'q', new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1, -1}, {1, -1}}
    );

    // 定义一个类来表示 棋子从 (x0, y0) 点出发，沿 (dx, dy) 方向移动 step 步 这样的操作
    private record Move(int x0, int y0, int dx, int dy, int step){}

    public int countCombinations(String[] pieces, int[][] positions) {
        int n = pieces.length;
        // 预处理，记录每个棋子所有可能的移动
        Move[][] moves = new Move[n][];
        for(int i = 0; i < n; i++) {
            moves[i] = generateMoves(positions[i][0], positions[i][1], PIECE_DIRECTIONS.get(pieces[i].charAt(0)));
        }
        Move[] path = new Move[n];
        return dfs(0, n, moves, path);
    }

    private Move[] generateMoves(int x0, int y0, int[][] directions) {
        List<Move> moves = new ArrayList<>();
        moves.add(new Move(x0, y0, 0, 0, 0)); // 添加初始位置
        for(int[] direction : directions) {
            // 按 step 迭代，得到棋子按某个方向移动可能到达的各个位置
            int x = x0 + direction[0], y = y0 + direction[1];
            for(int step = 1; 0 < x && x <= SIZE && 0 < y && y <= SIZE; step++) {
                moves.add(new Move(x0, y0, direction[0], direction[1], step));
                x += direction[0];
                y += direction[1];
            }
        }
        // List 转数组，这里构造的 Move 类型的数组限定了列表中的泛型
        return moves.toArray(Move[]::new);
    }

    // 判断有没有可能重叠
    private boolean check(Move m1, Move m2) {
        // 从两个起始位置出发
        int x1 = m1.x0, y1 = m1.y0;
        int x2 = m2.x0, y2 = m2.y0;
        for(int i = 0; i < Math.max(m1.step, m2.step); i++) {
            // 每次走一步
            if(i < m1.step) {
                x1 += m1.dx;
                y1 += m1.dy;
            }
            if (i < m2.step) {
                x2 += m2.dx;
                y2 += m2.dy;
            }
            // 重叠返回 false
            if (x1 == x2 && y1 == y2) {
                return false;
            }
        }
        return true;
    }

    private int dfs(int i , int n, Move[][] moves, Move[] path) {
        // 当前棋子下标越界，表示已经判断完可能重叠的情形，返回一种符合条件的结果
        if(i == n) {
            return 1;
        }
        int res = 0;
        // 定义循环控制标记，用来剪枝
        outer:
        for(Move move : moves[i]) {
            for(int j = 0; j < i; j++) {
                if(!check(move, path[j])) {
                    continue outer; // 出现重叠的情况，后面都不用尝试了，直接开始下一轮
                }
            }
            path[i] = move; // 记录路径
            res += dfs(i + 1, n, moves, path); // 进一步递归下一个棋子的情形
        }
        return res;
    }
}

梳理总结

record 关键字

在 Java 中，record 关键字是从 Java 14 引入的，它提供了一种简洁的方式来创建不可变的数据类。record 是一种特殊的类，它的主要用途是封装数据，特别适用于那些只包含属性（字段）并且需要自动实现 equals、hashCode 和 toString 方法的场景。

循环控制标记

在 Java 中，标记并跳出多重循环可以通过使用 标签 label 与 break 或 continue 结合来实现，标签可以用来指定退出哪一层循环：

• break [label]; 表示从标签位置开始执行，不再继续跳出的循环。
• break [label]; 表示从标签位置开始执行，从跳出的循环的下一轮次继续。

不常用，一般情况下不建议用，积累一下。