当前位置:首页 > 力扣 > 力扣LCP41题解析:棋盘翻转算法优化与C++深度优先搜索策略

力扣LCP41题解析:棋盘翻转算法优化与C++深度优先搜索策略

3天前

力扣LCP41题解析:棋盘翻转算法优化与C++深度优先搜索策略 力扣LCP41 棋盘翻转算法 动态规划 深度优先搜索 C++递归优化 第1张

一、题目解读

力扣LCP41题要求玩家在给定棋盘中,通过翻转单个棋子(将'.'变为'X'),使其周围'X'连锁翻转'O',最终计算最多能翻转多少棋子。题目核心在于探索局部翻转带来的全局连锁效应,需高效遍历并模拟翻转过程,寻找最优解。

二、解题思路

采用“局部试探+深度优先搜索DFS)”策略:

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题解

原创内容 转载请注明出处

分享给朋友:

相关文章

IOI 1994 洛谷1216:如何用O(1)空间解决数字三角形问题?附代码实现

IOI 1994 洛谷1216:如何用O(1)空间解决数字三角形问题?附代码实现

题目重解:数字三角形是一个经典的动态规划问题,给定一个由数字组成的三角形结构,从顶部出发,每次可以移动到下方相邻的数字,最终到达底部。我们需要找到一条路径,使得路径上经过的数字总和最大。这个问题可以很...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

一、题目解读CSP-J 2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记...

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

一、题目解读    “生命之树”是一道经典的树形结构问题,要求计算一棵带权树中,以某个节点为根的最大子树权值和。题目输入为n个节点及边信息,每个节点有权值wi,...

牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)

牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)

一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n-1条边构成,保证为连通无...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。