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表示不可以继续，反之遇到白色棋子则向该方向一直走，并判断该方向尾部方向是否为黑色棋子，如果是则满足要求，反之不可以。文章来源：https://www.toymoban.com/news/detail-493905.html
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())
{
//黑色可以走 直到最后是黑色就返回true
if(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://www.toymoban.com/news/detail-493905.html
到了这里，关于【每日一题】LCP 41. 黑白翻转棋的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
