图搜索 | LCP 41. 黑白翻转棋 *

本文记录的是刷题过程中的重要概念和笔记。如有侵权，请联系删除。

目录

• 原题
• 思路
• • 母题
  • 方法
  • 复杂度
  • 知识点
• 补充

原题

在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 “X”, 白棋记作字母 “O”，空余位置记作 “.”。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fHi6rV
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

母题

八皇后问题，没有快捷方法，回溯爆搜

方法

广度优先搜索+回溯

对每一个空余位置尝试黑棋放置，用一个队列来存储正在进行「翻转操作」的黑棋位置，若有可以翻转的白棋，则将这些白旗进行翻转，并加入队列中。直至队列为空表示一次放置黑棋结束。

class Solution {
private:const int dirs[8][2] = {// 1*：将可能的八个方向以字典记录下来，从而实现代码归一化{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};bool judge(vector<string>& chessboard, int x, int y, int dx, int dy){// 判断该方向是否符合条件x+=dx;y+=dy;while(0<=x && x<chessboard.size() && 0<=y && y<chessboard[0].size()){if(chessboard[x][y]=='X') return true;else if(chessboard[x][y]=='.') return false;x+=dx;y+=dy;}return false;}int check(vector<string> chessboard, int x, int y){
// 注意参数：chessboard按值传递，因为不同位置需要更新为原来的棋盘。本质为回溯的改为原值。// 回溯算法// 终止条件：if(chessboard[x][y]!='.') return 0;int res=0;// 逐层的遍历通过队列存储，本质上是采用bfsqueue<pair<int,int>> que;// 2*：que.push(pair(x,y));注意写法que.push(pair<int,int>(x,y));while(!que.empty()){// 处理当前队首节点pair<int, int> tmp = que.front();que.pop();for(int i=0;i<8;i++){if(judge(chessboard,tmp.first,tmp.second,dirs[i][0],dirs[i][1])){int xTmp= tmp.first+dirs[i][0];int yTmp= tmp.second+dirs[i][1];while(chessboard[xTmp][yTmp]!='X'){que.push(pair<int,int>(xTmp,yTmp));chessboard[xTmp][yTmp]='X';xTmp+=dirs[i][0];yTmp+=dirs[i][1];res++;}}}}return res;       }public:int flipChess(vector<string>& chessboard) {int res=0;for(int i=0;i<chessboard.size();i++){for(int j=0;j<chessboard[0].size();j++){if(chessboard[i][j]=='.')res=max(res,check(chessboard,i,j));}}return res;}
};

复杂度

知识点

• 1*：将可能的八个方向以字典记录下来，从而实现代码归一化
• 2*：que.push(pair(x,y));注意写法

补充

1. push_back和emplace_back的区别只在传入的参数是对象的构造参数时，如push_back(10)，emplace_back(10)。

   两种情况下：
   push_back(10)会先调用类的有参构造函数，创建一个临时对象，再在容器的末尾调用类的右值构造函数（因为这个临时对象没有名字，属于右值，所以只能使用右值构造函数），输入临时对象的地址，创建一个新的对象，根据地址值到临时对象所在的内存空间中拷贝数据，最后再调用临时对象的析构函数，析构这个临时对象。

   emplace_back(10)少了临时对象这一步，直接在容器的末尾调用类的有参构造函数创建一个新的对象，完成添加操作。

版权声明：本文为CSDN博主「Zeehoy」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44179561/article/details/124387475

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！