题目描述

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

「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。

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

样例

输入：
chessboard = ["....X.","....X.","XOOO..","......","......"]

输出：
3

解释：
可以选择下在 [2,4] 处，能够翻转白方三枚棋子。

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

输出：
2

解释：
可以选择下在 [2,2] 处，能够翻转白方两枚棋子。

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

输出：4

解释：
可以选择下在 [6,3] 处，能够翻转白方四枚棋子。

限制

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

算法

(暴力枚举) $O((mn)^4)$

1. 枚举每个空余位置，放入黑棋。
2. 放入后，对于每个白旗，枚举其 8 个方向是否合法，以及在合法情况下的最远距离。
3. 对于一对方向，如果都是合法的，则可以将范围内的白旗都填充为黑棋。

时间复杂度

• 最多有 $O(mn)$ 个空余位置。
• 每一轮遍历时，对于每个白旗，最多需要 $O(mn)$ 的时间检查。所以一轮遍历最多需要 $O((mn)^2)$ 时间。
• 最多有 $O(mn)$ 轮遍历，因为每次每轮遍历至少会将一个白旗变为黑棋。
• 故总时间复杂度为 $O((mn)^4)$，实际常数会非常小。

空间复杂度

• 需要 $O(mn)$ 的额外空间存储每次枚举的棋盘情况。

C++ 代码

const int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
const int dy[] = {-1, 1, -1, 1, 0, 0, 1, -1};

class Solution {
private:
    int m, n;

    bool valid(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    int operate(vector<string> &chessboard) {
        int tot = 0;

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (chessboard[i][j] != 'O')
                    continue;

                int len[8];
                for (int k = 0; k < 8; k++) {
                    int x = i, y = j;

                    len[k] = 0;
                    while (1) {
                        x += dx[k]; y += dy[k];
                        if (!valid(x, y) || chessboard[x][y] != 'O')
                            break;

                        len[k]++;
                    }

                    if (!valid(x, y) || chessboard[x][y] == '.')
                        len[k] = -1;
                }

                for (int k = 0; k < 8; k += 2) {
                    if (len[k] == -1 || len[k + 1] == -1)
                        continue;

                    for (int x = i, y = j; len[k] >= 0;
                    len[k]--, x += dx[k], y += dy[k])
                        if (chessboard[x][y] == 'O') {
                            tot++;
                            chessboard[x][y] = 'X';
                        }

                    for (int x = i, y = j; len[k + 1] >= 0;
                    len[k + 1]--, x += dx[k + 1], y += dy[k + 1])
                        if (chessboard[x][y] == 'O') {
                            tot++;
                            chessboard[x][y] = 'X';
                        }
                }
            }

        return tot;
    }

    int solve(vector<string> chessboard) {
        int tot = 0;

        while (1) {
            int t = operate(chessboard);
            if (t == 0)
                break;
            tot += t;
        }

        return tot;
    }

public:
    int flipChess(vector<string>& chessboard) {
        m = chessboard.size();
        n = chessboard[0].size();

        int ans = 0;

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (chessboard[i][j] == '.') {
                    chessboard[i][j] = 'X';
                    ans = max(ans, solve(chessboard));
                    chessboard[i][j] = '.';
                }

        return ans;
    }
};