【每日一题Day244】LCP 41. 黑白翻转棋 bfs dfs

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。