在?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;}}

總結

以上是生活随笔為你收集整理的3. 黑白翻转棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。