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

题目链接

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

分析

因为最多只有四个棋子，所以枚举每种可能的情况，回溯进行统计即可

代码实现

struct Step {
    int x, y, dx, dy, time; // 坐标、方向和步数
};

class Board {
private:
    const int BOARDSIZE = 8;
    int n = 0, ans = 0;
    vector<vector<Step>> moves;
    unordered_map<string, vector<pair<int, int>>> dir = {
        {"rook", {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}},
        {"bishop", {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}}},
        {"queen", {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}}}
    };

    // 生成可到的格子
    vector<Step> generatorMoves(string& pieces, vector<int>& position)
    {
        int x = position[0], y = position[1];
        vector<Step> tmoves = {{x, y, 0, 0, 0}};
        for(auto& [dx, dy] : dir[pieces])
        {
            int tx = x + dx, ty = y + dy;
            for(int i = 1; tx > 0 && tx <= BOARDSIZE && ty > 0 && ty <= BOARDSIZE; ++i)
            {
                tmoves.emplace_back(x, y, dx, dy, i);
                tx += dx, ty += dy;
            }
        }
        return tmoves;
    }

    // 判断所给的两步是否有冲突
    bool check(Step& a, Step& b)
    {
        int ax = a.x, ay = a.y, bx = b.x, by = b.y;
  
        for(int i = 0; i < max(a.time, b.time); ++i)
        {
            if(i < a.time)
                ax += a.dx, ay += a.dy;
            if(i < b.time)
                bx += b.dx, by += b.dy;
            if(ax == bx && ay == by)
                return false;
        }
        return true;
    }

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

        for(int i = 0; i < n; ++i)
            moves.emplace_back(generatorMoves(pieces[i], positions[i]));
    }

    // 回溯进行计算
    int play()
    {
        vector<Step> record(n);
        auto checkStep = [&](auto& checkStep, int idx) -> void {
            if(idx == n)
            {
                ans++;
                return ;
            }

            for(Step& s : moves[idx])
            {
                bool f = true;
                for(int j = 0; j < idx; j++)
                {
                    if(!check(s, record[j]))
                    {
                        f = false;
                        break;
                    }
                }
  
                if(f)
                {
                    record[idx] = s;
                    checkStep(checkStep, idx + 1);
                }
            }
        };
        checkStep(checkStep, 0);
        return ans;
    }
};


class Solution {
public:
    int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {
        Board thisGame(pieces, positions);
        thisGame.cm();
        return thisGame.play();
    }
};

复杂度分析

• 时间复杂度：$O(nST^n)$, 其中 $n$ 为棋子的个数，$S$ 为棋盘的大小，$T$ 为单个棋子的合法位置个数
• 空间复杂度：$O(nT)$