LCP 41. 黑白翻转棋
在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。
- 思路
枚举棋盘中每一个未下棋的位置，求出在该位置下黑子时，能够反转的白子数目，取最大值返回即可。对于每一个位置需要求出八个方向末尾是黑子的连续白子数目，并且如果将一个白子反转为黑子后，还需要搜索该位置延伸出去能够翻转的白子数目，故而可以使用bfs或者dfs实现
bfs
- 实现
将每个方向的可以反转的白子加入队列中
class Solution { String[] chessboard; int[][] dirs = {{0, 1},{0, -1}, {1, 0}, {-1, 0}, {1, -1}, {1, 1},{-1, 1}, {-1, -1}}; int m, n; public int flipChess(String[] chessboard) { m = chessboard.length; n = chessboard[0].length(); this.chessboard = chessboard; int res = 0; for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ if (chessboard[i].charAt(j) == '.'){ res = Math.max(res, bfs(i, j)); } } } return res; } // 使用bsf搜索在位置(x,y)下黑子时,能够反转的白子数目 // 将白子放入队列中，搜索八个方向末尾是黑子的连续白子数目 // 如果下一个位置是白子，那么继续放入队列 // 如果下一个位置是黑子，那么记录连续白子数目 // 如果下一个位置没有子，那么忽略不计 public int bfs(int x, int y){ char[][] chess = new char[m][n]; for (int i = 0; i < m; i++){ chess[i] = chessboard[i].toCharArray(); } int res = 0; Deque<int[]> queue = new LinkedList<>(); queue.addLast(new int[]{x, y}); chess[x][y] ='X'; while (!queue.isEmpty()){ int[] loc = queue.pollFirst(); x = loc[0]; y = loc[1]; for (int k = 0; k < 8; k++){ int i = x + dirs[k][0] , j = y + dirs[k][1]; while (i >= 0 && i < m && j >= 0 && j < n && chess[i][j] == 'O'){ i += dirs[k][0]; j += dirs[k][1]; } if (i >= 0 && i < m && j >= 0 && j < n && chess[i][j] == 'X'){ i -= dirs[k][0]; j -= dirs[k][1]; res += Math.max(Math.abs(x - i), Math.abs(y - j)); while (x != i || y != j){ chess[i][j] = 'X'; queue.addLast(new int[]{i, j}); i -= dirs[k][0]; j -= dirs[k][1]; } } } } return res; } }
dfs
- 实现
使用额外数组记录每个方向可以反转的白子位置，再进行dfs
class Solution { char[][] cb; int m,n; int ans = 0; int[] directions = new int[]{-1,-1,0,1,1,-1,1,0,-1}; public int flipChess(String[] chessboard) { m = chessboard.length; n = chessboard[0].length(); this.cb = new char[m][n]; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(chessboard[i].charAt(j)=='.'){ for(int t = 0; t < m; t++){ cb[t] = chessboard[t].toCharArray(); } ans = Math.max(ans,dfs(i,j)); } } } return ans; } private int dfs(int i, int j){ List<int[]> nexts = new ArrayList<>(); for(int index = 0; index < 8; index++){ int x = i+directions[index]; int y = j+directions[index+1]; List<int[]> tmp = new ArrayList<>(); while(x>=0&&x<m&&y>=0&&y<n&&cb[x][y]=='O'){ tmp.add(new int[]{x,y}); x+=directions[index]; y+=directions[index+1]; } if(x>=0&&x<m&&y>=0&&y<n&&cb[x][y]=='X'){ nexts.addAll(tmp); } } for(int[] next:nexts){ cb[next[0]][next[1]] = 'X'; } int ans = nexts.size(); for(int[] next:nexts){ ans += dfs(next[0],next[1]); } return ans; } } 作者：钰娘娘丿-曱-乀 链接：https://leetcode.cn/problems/fHi6rV/solutions/2315793/yu-niang-niang-lcp-41-hei-bai-fan-zhuan-yv1s6/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
