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

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

做题过程

一开始没有读懂题目，以为是用回溯，后面又看了一下题目，还有按照时间每秒一步，每次只能往某个固定方向移动，而且只需要考虑一些特定的矛盾情形，那么就感觉需要推导出公式，就没做下去了，看了题解还是枚举，其实就和推导公式一个类型了。

算法概述

本题要求为给出一张8*8的棋盘，棋盘上有“车”，“后”，“象”等棋子，每个棋子，每秒按照一个固定的方向移动一格，计算有多少种移动可能，如两个棋子在移动过程中恰巧相遇在同一格，则不包括当前组合。使用枚举和剪枝优化。

时间复杂度为
空间复杂度为O(n)

JAVA

class Solution {
    // 每种棋子的移动方向
    private static final Map<Character, int[][]> PIECE_DIRS = 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}} // 皇后
    );

    public int countCombinations(String[] pieces, int[][] positions) {
        int n = pieces.length;
        // 预处理所有合法移动
        Move[][] allMoves = new Move[n][];
        for (int i = 0; i < n; i++) {
            // 传入棋子类型的头字母和起始位置
            allMoves[i] = generateMoves(positions[i][0], positions[i][1], 
            PIECE_DIRS.get(pieces[i].charAt(0)));
        }

        Move[] path = new Move[n]; // 注意 path 的长度是固定的
        return dfs(0, n, allMoves, path);
    }

    // 起点 (x0,y0)，移动方向 (dx,dy)，移动次数 step
    private record Move(int x0, int y0, int dx, int dy, int step) {
    }

    // 计算位于 (x0,y0) 的棋子在 dirs 这些方向上的所有合法移动
    private Move[] generateMoves(int x0, int y0, int[][] dirs) {
        final int SIZE = 8;
        List<Move> moves = new ArrayList<>();
        // 原地不动也算
        moves.add(new Move(x0, y0, 0, 0, 0)); 
        // 枚举每个方向
        for (int[] d : dirs) 
            // 已经处理过原地不动，现在从动一步开始
            int x = x0 + d[0], y = y0 + d[1];
            for (int step = 1; 0 < x && x <= SIZE && 0 < y && y <= SIZE; step++) {
                // 每次不需要移动坐标，只需要记录不同方向最多可以走多少步
                moves.add(new Move(x0, y0, d[0], d[1], step));
                x += d[0];
                y += d[1];
            }
        }
        return moves.toArray(Move[]::new);
    }

    // 判断两个移动是否合法，即不存在同一时刻两个棋子重叠的情况
    private boolean isValid(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;
            }
            if (x1 == x2 && y1 == y2) { // 重叠
                return false;
            }
        }
        return true;
    }

    private int dfs(int i, int n, Move[][] allMoves, Move[] path) {
        // 能够枚举到最后一个棋子则说明是没有相遇的
        if (i == n) {
            return 1;
        }
        int res = 0;
        outer:
        // 枚举当前棋子的所有移动方向
        for (Move move1 : allMoves[i]) {
            // 判断合法移动 move1 是否有效
            for (int j = 0; j < i; j++) {
                if (!isValid(move1, path[j])) {
                    continue outer; // 无效，枚举下一个 move1
                }
            }
            // 用于记录棋子当前的临时移动状态
            path[i] = move1; 
            // 枚举其他棋子在同一方向下的临时移动方向
            res += dfs(i + 1, n, allMoves, path);
        }
        return res;
    }
}

重要实例方法及属性(JAVA)

Map.of()：创建 不可变 的Map对象(Java9)
private record Move(int x0, int y0, int dx, int dy, int step) {}：创建简单的 数据载体类，自动生成了构造方法、toString 方法、equals 方法、hashCode 方法以及访问器方法 (java14)
outer:：设置一个可跳转的标签，类似goto

总结

虽然只是暴力枚举，但难度重点在于 对于语言的理解 ，如果不了解新特性和快速搭建解法的框架，则需要非常冗长的代码来实现，需要背记。