LCP 41. 黑白翻转棋

LC每日一题，参考LCP 41. 黑白翻转棋。

题目

在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。
注意：

• 若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋
• 输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置

输入：chessboard = [".X.",".O.","XO."]
输出：2

输入：chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]
输出：4

提示：

• 1 <= chessboard.length, chessboard[i].length <= 8
• chessboard[i] 仅包含 "."、"O" 和 "X"

解题思路

• 深度优先搜索：对棋盘中每个可以填黑棋的位置.进行深度优先搜索,同时翻转白棋变为黑棋后需要对该黑棋深度优先搜索,也可以使用广度优先搜索用队列维护新的搜索点。

深度优先搜索

class Solution {
    int n,m;
    String[] chessboard;
    public int flipChess(String[] chessboard) {
        this.chessboard = chessboard;
        n = chessboard.length;
        m = chessboard[0].length();
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(chessboard[i].charAt(j) == '.') { //可以放置黑棋
                    ans = Math.max(ans,get(i,j,newC()));
                }
            }
        }
        return ans;
    }
    //创建新的棋盘拷贝
    char[][] newC() {
        char[][] c = new char[n][m];
        for(int i = 0; i < n; i++) c[i] = chessboard[i].toCharArray();
        return c;
    }
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
    //在i,j位置放置黑棋翻转的白棋数
    int get(int i, int j,char[][] cb) {
        int count = 0;
        //判断周围有没有白棋
        for(int[] dir : dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if(ni >= 0 && nj >= 0 && ni < n && nj < m && cb[ni][nj] == 'O') {
                //往dir方向继续找看有没有黑棋
                count += check(dir,ni,nj,cb);
            }
        }
        return count;
    }
    //返回能翻转该方向白棋的数量
    int check(int[] dir, int i, int j,char[][] cb) {
        //判断终点是否有黑棋
        int ni = i + dir[0],nj = j + dir[1];
        while(ni >= 0 && nj >= 0 && ni < n && nj < m && cb[ni][nj] == 'O') {
            ni += dir[0];
            nj += dir[1];
        }
        if(!(ni >= 0 && nj >= 0 && ni < n && nj < m) || cb[ni][nj] != 'X') return 0;
        //翻转白棋 统计数量
        int count = 0;
        ni = i;
        nj = j;
        while(ni >= 0 && nj >= 0 && ni < n && nj < m && cb[ni][nj] == 'O') {
            cb[ni][nj] = 'X';
            count += 1 + get(ni,nj,cb);//递归获取该黑棋的翻转数
            ni += dir[0];
            nj += dir[1];
        }
        return count;
    }
}

复杂度分析

• 时间复杂度：O(n^2m^2max(n,m)，枚举位置nm,dfs搜索nm x max(n.m)。
• 空间复杂度：O(n^2m^2),复制棋盘nm大小复制了nm次。

2023.06.21