把所有不和边界的O相连接的O都置为X.
思路: 从边界的O出发，把所有和它相连的O都置为@，dfs递归调用；
再遍历一边，把所有O置为X，再把@重新置为O.
注意重置的时候的顺序，不能先把@置为O,在把O置为X.这样会把@也置为X.
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
if not board:
return board
self.m = len(board)
self.n = len(board[0])
self.board = board
for i in [0, self.m - 1]:
for j in range(self.n):
if self.board[i][j] == "O":
self.dfs(i, j)
for j in [0, self.n - 1]:
for i in range(1, self.m - 1):
if self.board[i][j] == "O":
self.dfs(i, j)
for i in range(0, self.m):
for j in range(0, self.n):
if self.board[i][j] == "O":
self.board[i][j] = "X"
if self.board[i][j] == "@":
self.board[i][j] = "O"
return self.board
def dfs(self, i, j):
self.board[i][j] = "@"
di = [0, 0, -1, 1]
dj = [-1, 1, 0, 0]
for k in range(4):
ni = i + di[k]
nj = j + dj[k]
if (0 <= ni < self.m) and (0 <= nj < self.n):
if self.board[ni][nj] == "O":
self.dfs(ni, nj)
s = Solution()
res = s.solve([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]])
print(res)
