title
在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。
「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。
注意：
- 若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋
- 输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置
示例 1：
输入：
chessboard = ["....X.","....X.","XOOO..","......","......"]输出：
3解释： 可以选择下在
[2,4]处，能够翻转白方三枚棋子。
示例 2：
输入：
chessboard = [".X.",".O.","XO."]输出：
2解释： 可以选择下在
[2,2]处，能够翻转白方两枚棋子。
示例 3：
输入：
chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]输出：
4解释： 可以选择下在
[6,3]处，能够翻转白方四枚棋子。
提示：
1 <= chessboard.length, chessboard[i].length <= 8chessboard[i]仅包含"."、"O"和"X"
solution
BFS
dirs8 = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
dirs4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
class Solution:
def handle(self, chessboard: List[str], i, j) -> int:
m, n = len(chessboard), len(chessboard[0])
for k in range(m):
chessboard[k] = list(chessboard[k])
chessboard[i][j] = "X"
import collections
q = collections.deque()
q.append((i, j))
ans = 0
while q:
x, y = q.popleft()
for ax, ay in dirs8:
nx, ny = x + ax, y + ay
white = []
while True:
if nx < 0 or nx >= m or ny < 0 or ny >= n:
break
if chessboard[nx][ny] == ".":
break
elif chessboard[nx][ny] == "O":
white.append((nx, ny))
nx, ny = nx + ax, ny + ay
else:
for l in white:
q.append(l)
chessboard[l[0]][l[1]] = "X"
ans += 1
break
return ans
def flipChess(self, chessboard: List[str]) -> int:
import copy
if not chessboard:
return 0
m, n = len(chessboard), len(chessboard[0])
ans = 0
for i in range(m):
for j in range(n):
v = chessboard[i][j]
if v == ".":
cb = copy.deepcopy(chessboard)
t = self.handle(cb, i, j)
ans = max(ans, t)
return ans