【每日一题】LCP 41. 黑白翻转棋
- LCP 41. 黑白翻转棋
- 题目描述
- 解题思路
LCP 41. 黑白翻转棋
题目描述
在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 “X”, 白棋记作字母 “O”，空余位置记作 “.”。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。
力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。
注意：
若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋
输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置
示例 1：
输入：chessboard = ["....X.","....X.","XOOO..","......","......"]输出：3解释： 可以选择下在 [2,4] 处，能够翻转白方三枚棋子。
示例 2：
输入：chessboard = [".X.",".O.","XO."]输出：2解释： 可以选择下在 [2,2] 处，能够翻转白方两枚棋子。
示例 3：
输入：chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]输出：4解释： 可以选择下在 [6,3] 处，能够翻转白方四枚棋子。
提示：
1 <= chessboard.length, chessboard[i].length <= 8
chessboard[i] 仅包含 “.”、“O” 和 “X”
解题思路
思路：广度优先搜索。遍历棋盘，使用bfs求解从每一个空位置(x,y)出发所能翻转的最大棋子数，注意，每次枚举的时候不要更改原棋盘。bfs每次将(x,y)加入队列，然后弹出队头元素，从队头位置向四面八方开始搜索，在搜索前首先使用judge判断该位置是否可以行走，如果可以则将该位置翻转为黑色棋子，将其加入队列，并向该方向行走，再将翻转棋子数量加一。judge遇到黑色棋子则返回true表示可以继续走，遇到空白位置则返回false表示不可以继续，反之遇到白色棋子则向该方向一直走，并判断该方向尾部方向是否为黑色棋子，如果是则满足要求，反之不可以。
int dirs[8][2]={{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(x>=0&&x<chessboard.size()&&y>=0&&y<chessboard[0].size()){//黑色可以走 直到最后是黑色就返回trueif(chessboard[x][y]=='X')return true;//空格不能走if(chessboard[x][y]=='.')return false;//白色则向这个方向一直走x+=dx;y+=dy;}return false;
}
//注意 每次枚举不要改变原棋盘
//bfs(c,x,y)表示在(x,y)位置放置黑棋所能翻转的棋子数
int bfs(vector<string> chessboard,int px,int py)
{int cnt=0;queue<pair<int,int>> q;q.emplace(px,py);chessboard[px][py]='X';while(!q.empty()){auto t=q.front();q.pop();//从当前向四面八方搜索for(int i=0;i<8;i++){//首先判断该方向是否被包围if(judge(chessboard,t.first,t.second,dirs[i][0],dirs[i][1])){//然后向该方向行走int x=t.first+dirs[i][0],y=t.second+dirs[i][1];while(chessboard[x][y]!='X'){//该方向被翻转 可以继续判断是否可以行走q.emplace(x,y);chessboard[x][y]='X';x+=dirs[i][0];y+=dirs[i][1];//翻转数量加一cnt++;}}}}return cnt;
}
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,bfs(chessboard,i,j));}}return res;
}
总结：注意，使用方向数组简化判断。
本文链接：https://my.lmcjl.com/post/3174.html
展开阅读全文
4 评论