2024年第49周力扣打卡

[XLXXLXXLX]

周一

n皇后II
好久不写了，脑袋木掉了。
总之就是回溯+状态压缩（位运算），用三个比特集合存储横行、左斜行、右斜行的情况，然后按列扫描并回溯就好。
用到了std::bitset，这个感觉还算有点用。

class Solution {
public:
    std::bitset<10>col{0};
    std::bitset<20>diag1{0}, diag2{0};
    int cnt{0};
    void queen(int row, int n){
        if(row == n){
        // std::cout<<"row = "<<row<<'\n';
        // std::cout<<col.to_string()<<'\n';
        // std::cout<<diag1.to_string()<<'\n';
        // std::cout<<diag2.to_string()<<'\n';
            cnt++;
            return;
        }
        for(int i = 0; i < n; i++){
        // 左斜行和右斜行的idx搞对就好
            if(!col[i] && !diag1[i + row] && !diag2[i + n - 1 - row]){
                col[i] = 1;
                diag1[i + row] = 1;
                diag2[i + n - 1 - row] = 1;
                queen(row + 1, n);
                col[i] = 0;
                diag1[i + row] = 0;
                diag2[i + n - 1 - row] = 0;
            }
        }
    }
    int totalNQueens(int n) {
        queen(0, n);
        return cnt;
    }
};

周二

感冒了，正好出了一道eazy，签个到算了
3274. 检查棋盘方格颜色是否相同

class Solution {
public:
    bool checkTwoChessboards(string coordinate1, string coordinate2) {
        return !((coordinate1[0] - 'a' + coordinate1[1] - '1' 
                + coordinate2[0] - 'a' + coordinate2[1] - '1') % 2);
    }
};

周三

2056. 棋盘上有效移动组合的数目
hard，头痛牙痛，脑袋蒙蒙，知道要用回溯/搜索，但就是搞不对，感觉是对数据结构的组织不太好。下面是别人的解法：

struct Move {
    int x0, y0; // 起点
    int dx, dy; // 移动方向
    int step;   // 移动次数
};

class Solution {
    vector<pair<int, int>> DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1, -1}, {1, -1}}; // 上下左右 + 斜向
    unordered_map<char, vector<pair<int, int>>> PIECE_DIRS = {
        {'r', {DIRS.begin(), DIRS.begin() + 4}},
        {'b', {DIRS.begin() + 4, DIRS.end()}},
        {'q', DIRS},
    };

    // 计算位于 (x0,y0) 的棋子在 dirs 这些方向上的所有合法移动
    vector<Move> generate_moves(int x0, int y0, vector<pair<int, int>>& dirs) {
        const int SIZE = 8;
        vector<Move> moves = {{x0, y0, 0, 0, 0}}; // 原地不动
        for (auto [dx, dy] : dirs) {
            // 往 d 方向走 1,2,3,... 步
            int x = x0 + dx, y = y0 + dy;
            for (int step = 1; 0 < x && x <= SIZE && 0 < y && y <= SIZE; step++) {
                moves.emplace_back(x0, y0, dx, dy, step);
                x += dx;
                y += dy;
            }
        }
        return moves;
    }

    // 判断两个移动是否合法，即不存在同一时刻两个棋子重叠的情况
    bool is_valid(Move& m1, Move& m2) {
        int x1 = m1.x0, y1 = m1.y0;
        int x2 = m2.x0, y2 = m2.y0;
        for (int i = 0; i < 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;
    }

public:
    int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {
        int n = pieces.size();
        // 预处理所有合法移动
        vector<vector<Move>> all_moves(n);
        for (int i = 0; i < n; i++) {
            all_moves[i] = generate_moves(positions[i][0], positions[i][1], PIECE_DIRS[pieces[i][0]]);
        }

        vector<Move> path(n); // 注意 path 的长度是固定的
        int ans = 0;
        auto dfs = [&](auto& dfs, int i) -> void {
            if (i == n) {
                ans++;
                return;
            }
            // 枚举当前棋子的所有合法移动
            for (Move& move1 : all_moves[i]) {
                // 判断合法移动 move1 是否有效
                bool ok = true;
                for (int j = 0; j < i; j++) {
                    if (!is_valid(move1, path[j])) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    path[i] = move1; // 直接覆盖，无需恢复现场
                    dfs(dfs, i + 1); // 枚举后续棋子的所有合法移动组合
                }
            }
        };
        dfs(dfs, 0);
        return ans;
    }
};

周四

3001. 捕获黑皇后需要的最少移动次数
模拟题，搞对就行，没啥特别的，但要注意浮点数精度

class Solution {
public:
    int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        if((c + d + e + f) % 2 == 1){
            //cout << "白色象和黑皇后不在同一种颜色的格子里，只能使用车来捕获\n";
            if(a == e || b == f){
                //cout << "车和皇后在同一行/同一列\n";
                if(a == c && a == e && (d - b) * (d - f) < 0){
                    //cout << "象在车和皇后中间\n";
                    return 2;
                }else if(b == d && b == f && (c - a) * (c - e) < 0){
                    //cout << "象在车和皇后中间\n";
                    return 2;
                }
                return 1;
            }
            //cout << "不在同一行/同一列\n";
            return 2;
        }
        // 可能是车，可能是象
        if(a == e || b == f){
            //cout << "车和皇后在同一行/同一列\n";
            if(a == c && a == e && (d - b) * (d - f) < 0){
                //cout << "象在车和皇后中间\n";
                return 2;
            }else if(b == d && b == f && (c - a) * (c - e) < 0){
                //cout << "象在车和皇后中间\n";
                return 2;
            }
            return 1;
        }
        if(float k = e == c ? 0 : float(f - d) / (e - c);
                abs(abs(k) - 1) < 0.0001){
            //cout << "象和皇后在同一个斜线\n";
            float k1 = float(f - b) / (e - a);
            if(abs(k - k1) < 0.0001){
                //cout << "斜率相同\n";
                if((b - d) * (b - f) < 0){
                    //cout << "车在象和皇后中间\n";
                    return 2;
                }
            }
            return 1;
        }
        //cout << "普通情况\n";
        return 2;
    }
};

周五

999. 可以被一步捕获的棋子数
easy，抄答案了

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        int cnt = 0, st = 0, ed = 0;
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    st = i;
                    ed = j;
                    break;
                }
            }
        }
        for (int i = 0; i < 4; ++i) {
            for (int step = 0;; ++step) {
                int tx = st + step * dx[i];
                int ty = ed + step * dy[i];
                if (tx < 0 || tx >= 8 || ty < 0 || ty >= 8 || board[tx][ty] == 'B') {
                    break;
                }
                if (board[tx][ty] == 'p') {
                    cnt++;
                    break;
                }
            }
        }
        return cnt;
    }
};

周六

688. 骑士在棋盘上的概率
mid，偷懒了，暴力搜索没写出来，看了答案，挺普通的dp

class Solution {
public:
    vector<vector<int>> dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n)));
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) { dp[step][i][j] = 1; } 
                    else {
                        for (auto & dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
};