题目描述

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions，其中 positions[i] = [r_i, c_i] 表示第 i 个棋子现在在棋盘上的位置为 (r_i, c_i)，棋盘下标从 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 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效。

请你返回 有效 移动组合的数目。

注意：

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

样例

输入：pieces = ["rook"], positions = [[1,1]]
输出：15
解释：上图展示了棋子所有可能的移动。

输入：pieces = ["queen"], positions = [[1,1]]
输出：22
解释：上图展示了棋子所有可能的移动。

输入：pieces = ["bishop"], positions = [[4,3]]
输出：12
解释：上图展示了棋子所有可能的移动。

输入：pieces = ["rook","rook"], positions = [[1,1],[8,8]]
输出：223
解释：每个车有 15 种移动，所以总共有 15 * 15 = 225 种移动组合。
但是，有两个是不有效的移动组合：
- 将两个车都移动到 (8, 1)，会导致它们在同一个格子相遇。
- 将两个车都移动到 (1, 8)，会导致它们在同一个格子相遇。
所以，总共有 225 - 2 = 223 种有效移动组合。
注意，有两种有效的移动组合，分别是一个车在 (1, 8)，另一个车在 (8, 1)。
即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。

输入：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 个是有效的。

限制

• n == pieces.length
• n == positions.length
• 1 <= n <= 4
• pieces 只包含字符串 "rook"，"queen" 和 "bishop"。
• 棋盘上总共最多只有一个后。
• 1 <= x_i, y_i <= 8
• 每一个 positions[i] 互不相同。

算法

(递归回溯) $O((n(r + c)) ^ n)$

1. 按顺序以此枚举每个棋子的目标位置，并记录当前棋子到达该位置的路径信息。
2. 递归时，分别判断当前棋子是否可以作为目标位置，以及是否可以继续在该方向上继续移动。

时间复杂度

• 每一层递归，都需要 $O(n(r + c))$ 的时间判断和枚举情况。
• 故总时间复杂度为 $O((n(r + c))^n)$。

空间复杂度

• 需要 $O(nrc)$ 的额外空间记录所有棋子的路径信息已经递归调用的系统栈。

C++ 代码

const int dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};

const int dr[] = {0, 2, 4, 6};
const int dq[] = {0, 1, 2, 3, 4, 5, 6, 7};
const int db[] = {1, 3, 5, 7};

class Solution {
private:
    int n, ans;
    int step[4][9][9];
    int ed[4][3];

    bool check_end(int c, int tx, int ty, int cnt) {
        // 检查 (tx, ty) 在第 cnt 步是否可以作为终点。
        // 如果之前 (tx, ty) 有过超过 cnt 步才经过的情况，则 (tx, ty) 不允许为终点。

        for (int i = 0; i < c; i++)
            if (step[i][tx][ty] >= cnt)
                return false;

        return true;
    }

    bool check_pass(int c, int tx, int ty, int cnt) {
        // 检查 (tx, ty) 第 cnt 步是否可以经过。
        // 如果之前 (tx, ty) 也在第 cnt 经过，
        // 或者之前有过在 (tx, ty) 的终点且其达到终点的步数小于等于 cnt，
            // 则 (tx, ty) 不允许经过。

        for (int i = 0; i < c; i++) {
            if (step[i][tx][ty] == cnt)
                return false;

            if (ed[i][0] == tx && ed[i][1] == ty && ed[i][2] <= cnt)
                return false;
        }

        return true;
    }


    void solve(int c, const vector<string> &pieces,
        const vector<vector<int>>& positions
    ) {
        if (c == n) {
            ans++;
            return;
        }

        int x = positions[c][0], y = positions[c][1];
        memset(step[c], -1, sizeof(step[c]));
        ed[c][0] = x; ed[c][1] = y; ed[c][2] = 0;

        step[c][x][y] = 0;
        if (check_end(c, x, y, 0))
            solve(c + 1, pieces, positions);

        if (!check_pass(c, x, y, 0))
            return;

        vector<int> dir;

        if (pieces[c] == "rook") dir = vector<int>{dr, dr + 4};
        else if (pieces[c] == "queen") dir = vector<int>{dq, dq + 8};
        else dir = vector<int>{db, db + 4};

        for (int d : dir) {
            memset(step[c], -1, sizeof(step[c]));
            step[c][x][y] = 0;
            int tx = x + dx[d], ty = y + dy[d], cnt = 1;

            while (tx >= 1 && tx <= 8 && ty >= 1 && ty <= 8 &&
                check_pass(c, tx, ty, cnt)
            ) {
                step[c][tx][ty] = cnt;
                ed[c][0] = tx; ed[c][1] = ty; ed[c][2] = cnt;
                if (check_end(c, tx, ty, cnt))
                    solve(c + 1, pieces, positions);

                tx += dx[d]; ty += dy[d];
                cnt++;
            }
        }
    }

public:
    int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {
        n = pieces.size();

        ans = 0;
        solve(0, pieces, positions);

        return ans;
    }
};