力扣LCP41题解析:棋盘翻转算法优化与C++深度优先搜索策略
一、题目解读
力扣LCP41题要求玩家在给定棋盘中,通过翻转单个棋子(将'.'变为'X'),使其周围'X'连锁翻转'O',最终计算最多能翻转多少棋子。题目核心在于探索局部翻转带来的全局连锁效应,需高效遍历并模拟翻转过程,寻找最优解。
二、解题思路
1. 遍历棋盘每个空白点:以每个'.'为起点,尝试翻转。
2. 方向向量优化:定义8个方向向量,模拟周围棋子扩散。
3. 递归翻转连锁反应:通过countFlips()函数,逐层遍历方向路径,若遇到'X'则终止并统计翻转次数。
4. 动态更新最大值:记录所有试探中的最大翻转数,最终返回结果。
三、解题步骤
1. 初始化变量:获取棋盘尺寸m×n,定义方向向量dirs[8][2],max_flips初始化为0。
2. 外层循环遍历棋盘:对每个位置(i,j),若为'.'则进入翻转试探。
3. 临时棋盘模拟翻转:复制原棋盘temp,将(i,j)置为'X'。
4. 递归计算连锁翻转:调用countFlips(temp,i,j),统计该路径下翻转次数。
5. 更新最大值:比较当前翻转数与max_flips,取较大值。
6. 方向遍历细节:countFlips()中,沿8个方向扩散,遇'O'则记录待翻转坐标,遇'X'则终止并递归处理链式翻转(调用flipChain())。
四、代码与注释
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,1}}; // 方向向量复用(可优化) 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 < m && ny >= 0 && ny < n) { // 边界检查 if (board[nx][ny] == 'O') { // 遇'O'则记录 to_flip.emplace_back(nx, ny); nx += dx; ny += dy; // 继续扩散 } else if (board[nx][ny] == 'X') { // 遇'X'终止 for (auto [i,j] : to_flip) { // 翻转已记录的'O' 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; } };
五、总结
该解法巧妙结合局部试探与DFS,通过方向向量减少重复计算,利用临时棋盘避免原数据污染。优化点包括:方向向量的复用、边界判断的提前终止条件、递归函数的精简设计。时间复杂度取决于棋盘大小与试探次数,可进一步通过剪枝策略优化性能。
参考:力扣LCP41题解
原创内容 转载请注明出处