棋盘翻转大师：力扣LCP41题"翻转黑白棋"深度解析

一、问题理解

题目要求在一个黑白棋棋盘上找出一个空位('.'表示)，当放置一个黑棋('X')后，能够翻转最多数量的白棋('O')。翻转规则遵循标准黑白棋规则：在一条直线上，两个黑棋之间的所有白棋都会被翻转。

二、核心算法思路

1. 双层遍历：检查棋盘每个空位

2. 八方向探测：每个方向模拟落子后的翻转效果

3. 递归翻转：处理连锁翻转反应

三、完整代码解析

class Solution {
public:
    int flipChess(vector<string>& 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;
    }
};

四、关键知识点

1. 方向数组应用：使用8方向向量简化方向遍历

2. 递归思维：通过flipChain函数处理连锁反应

3. 棋盘复制技巧：使用temp副本避免修改原棋盘

五、实际应用

这种棋盘模拟+递归搜索的方法也适用于：

• 五子棋AI评估

• 围棋局面分析

• 其他棋盘类游戏逻辑实现

参考：编程资料