2025年3. 黑白翻转棋

大家好，我是讯享网，很高兴认识大家。

在 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 模拟，对每个棋盘先拷贝一份，尝试修改每个空位，并更新变黑棋子的最大值。

具体 BFS 逻辑为： 1.在空格附近的8个格子里找是否有非空格的 2.如果有则顺着这个方向继续找黑色棋子,并更新黑色路径的最大长度 3.找到黑色棋子则把该路径上的白色棋子置为黑色，并加入队列，继续BFS 4.将最多变黑的棋子数量返回

code：

class Solution { int m, n; int[][] dir = { 
  
    
  {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}}; public int flipChess(String[] chessboard) { this.m = chessboard.length; this.n = chessboard[0].length(); int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (chessboard[i].charAt(j) == '.') { char[][] clone = copy(chessboard); res = Math.max(res, flipOnlyOneChess(clone, i, j)); } } } return res; } private char[][] copy(String[] chessboard) { char[][] cs = new char[m][n]; for (int i = 0; i < m; i++) { cs[i] = chessboard[i].toCharArray(); } return cs; } public int flipOnlyOneChess(char[][] clone, int x0, int y0) { int max = Math.max(m, n), ans = 0; //原节点置黑 clone[x0][y0] = 'X'; Queue<int[]> queue = new LinkedList<>(); queue.add(new int[]{x0, y0}); while (!queue.isEmpty()) { int[] p = queue.poll(); //遍历8个方向 for (int[] d : dir) { int x = p[0] + d[0], y = p[1] + d[1]; if (!isValid(x, y, m, n) || clone[x][y] == '.') continue; int len = 0; for (int i = 0; i < max; i++) { //顺着这个方向继续找黑色棋子 int nx = x + d[0] * i, ny = y + d[1] * i; if (!isValid(nx, ny, m, n)) continue; char c = clone[nx][ny]; //若该方向上有空白棋子，则直接中断退出 if (c == '.') { break; //找到则将黑色路径的长度更新 } else if (c == 'X') len = i + 1; } for (int i = 0; i < len; i++) { int nx = x + d[0] * i, ny = y + d[1] * i; if (!isValid(nx, ny, m, n)) continue; char c = clone[nx][ny]; //如果路径上有白色棋子，则计数并加入队列 if (c == 'O') { ans++; queue.add(new int[]{nx, ny}); clone[nx][ny] = 'X'; } } } } return ans; } private boolean isValid(int x, int y, int m, int n) { return x >= 0 && x < m && y >= 0 && y < n; } }

讯享网

相关推荐