截图未命名.jpg 棋盘翻转大师：力扣LCP41题"翻转黑白棋"深度解析 递归算法 方向向量 力扣LCP41 C++ 第1张 一、问题理解 题目要求在一个黑白棋棋盘上找出一个空位('.'表示)，当放置一个黑棋('X')后，能够翻转最多数量的白棋('O')。翻转规则遵循标准黑白棋规则：在一条直线上，两个黑棋之间的所有白棋都会被翻转。

二、核心算法思路 双层遍历：检查棋盘每个空位 八方向探测：每个方向模拟落子后的翻转效果 递归翻转：处理连锁翻转反应 三、完整代码解析 class Solution { public: int flipChess(vector& chessboard) { int m = chessboard.size(), n = chessboard[0].size(); int max_flips = 0; // 记录最大翻转数

    // 8个方向向量：上、下、左、右、四个对角线
    int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},
                     {0,-1},        {0,1},
                     {1,-1}, {1,0}, {1,1}};

    // 遍历棋盘每个位置
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (chessboard[i][j] == '.') {  // 发现空位
                vector<string> temp = chessboard;  // 复制棋盘
                temp[i][j] = 'X';  // 模拟落子
                int flips = countFlips(temp, i, j);  // 计算翻转数
                max_flips = max(max_flips, flips);  // 更新最大值
            }
        }
    }
    return max_flips;
}

// 计算单次落子后的翻转数量
int countFlips(vector<string>& board, int x, int y) {
    int flips = 0;
    int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},
                     {0,-1},        {0,1},
                     {1,-1}, {1,0}, {1,1}};

    // 检查8个方向
    for (auto& dir : dirs) {
        int dx = dir[0], dy = dir[1];
        int nx = x + dx, ny = y + dy;
        vector<pair<int,int>> to_flip;  // 记录待翻转位置

        // 沿当前方向搜索
        while (nx >= 0 && nx < board.size() && 
               ny >= 0 && ny < board[0].size()) {
            if (board[nx][ny] == 'O') {  // 遇到白棋
                to_flip.emplACe_back(nx, ny);
                nx += dx;
                ny += dy;
            } 
            else if (board[nx][ny] == 'X') {  // 遇到黑棋，可以翻转
                for (auto [i,j] : to_flip) {
                    board[i][j] = 'X';  // 执行翻转
                    flips++;
                }
                flips += flipChain(board, to_flip);  // 处理连锁反应
                break;
            } 
            else {  // 遇到空位，终止搜索
                break;
            }
        }
    }
    return flips;
}

// 处理连锁翻转
int flipChain(vector<string>& board, vector<pair<int,int>>& positions) {
    int additional = 0;
    for (auto [x,y] : positions) {
        additional += countFlips(board, x, y);  // 递归计算新增翻转
    }
    return additional;
}

}; 四、关键知识点 方向数组应用：使用8方向向量简化方向遍历 递归思维：通过flipChain函数处理连锁反应 棋盘复制技巧：使用temp副本避免修改原棋盘 五、实际应用 这种棋盘模拟+递归搜索的方法也适用于：

参考：编程资料