黑白翻转棋

这个题解的思路是通过模拟下棋的过程来寻找最优的下棋位置。首先，遍历棋盘上的每一个空位（'.'），尝试在这个位置放置黑棋（'X'），然后从这个位置向八个方向（上、下、左、右、四个对角线方向）探索，查看是否可以通过放置这个棋子来翻转周围的白棋（'O'）。如果在某个方向上，从当前位置出发，连续遇到白棋后再遇到一个黑棋，那么这一路上的所有白棋都可以被翻转成黑棋。每次模拟下棋后，计算可以翻转的白棋数量，并更新最大值。最后返回最大的翻转数量。

时间复杂度: O(n^4)

空间复杂度: O(n^2)

class Solution:
    def flipChess(self, board: List[str]) -> int:
        m, n = len(board), len(board[0])
        def search(r,c):
            que = [(r,c)] # 用于存储需要检查的棋子位置
            grid = [list(row) for row in board] # 创建棋盘的副本
            grid[r][c] = 'X' # 在指定位置放置黑棋
            count = 0
            while len(que)>0:
                r,c = que.pop()
                for x_step, y_step in directions:
                    x, y = r+x_step, c+y_step
                    while 0<=x<m and 0<=y<n and grid[x][y] == 'O':
                        x, y = x + x_step, y + y_step
                    if 0<=x<m and 0<=y<n and grid[x][y] == 'X':
                        x, y = x - x_step,  y - y_step
                        count += max(abs(x-r), abs(y-c))
                        while x!=r or y!=c:
                            grid[x][y] = 'X'
                            que.append((x,y))
                            x, y = x - x_step, y - y_step
            return count
        directions = [(x_step, y_step) for x_step in range(-1,2) for y_step in range(-1,2) if x_step!=0 or y_step!=0]
        return max(search(r,c) for r in range(m) for c in range(n) if board[r][c] == '.')