Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
For example, X X X X X O O X X X O X X O X X
After running your function, the board should be: X X X X X X X X X X X X X O X X
用了DFS，发现会内存溢出。思路如下，对于边际上的每一个’O’，找到他们的连通分量，设置为’S’。之后将’O’设置为’X’，将’S’设置为’O’。代码如下：
class Solution(object): def dfs(self, i, j, board): if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]): return if board[i][j] == 'O': board[i][j] = 'q' self.dfs(i, j+1, board) self.dfs(i, j-1, board) self.dfs(i-1, j, board) self.dfs(i+1, j, board) def solve(self, board): """ :type board: List[List[str]] :rtype: void Do not return anything, modify board in-place instead. """ if len(board) != 0: for i in range(len(board)): if i == 0 or i == len(board) - 1: for j in range(len(board[0])): if board[i][j] == 'O': self.dfs(i, j, board) else: for j in [0, len(board[0]) - 1]: if board[i][j] == 'O': self.dfs(i, j, board) for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == 'O': board[i][j] = 'X' for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == 'q': board[i][j] = 'O'这样想来，这一类题目还是用Union-find让人觉得更安心一点。
class UF(object): def union(self, a, b, tmp_board, size): p = self.root(a, tmp_board) q = self.root(b, tmp_board) if p == q: return if size[p] > size[q]: tmp_board[q] = p size[p] += size[q] else: tmp_board[p] = q size[q] += size[p] def root(self, a, tmp_board): while(tmp_board[a] != a): tmp_board[a] = tmp_board[tmp_board[a]] a = tmp_board[a] return a def connected(self, a, b, tmp_board): return self.root(a, tmp_board) == self.root(b, tmp_board) class Solution(object): def solve(self, board): """ :type board: List[List[str]] :rtype: void Do not return anything, modify board in-place instead. """ m = len(board) uf = UF() if m == 0: return n = len(board[0]) tmp_board = [i for i in range(m*n+1)] size = [1] * (m*n+1) for i in range(m): for j in range(n): if board[i][j] == 'O': if j+1 < n: if board[i][j+1] == 'O': uf.union(i*n+j, i*n+j+1, tmp_board, size) if i+1 < m: if board[i+1][j] == 'O': uf.union((i+1)*n+j, i*n+j, tmp_board, size) for i in range(m): if i == 0 or i == m-1: for j in range(n): uf.union(m*n, i*n+j, tmp_board, size) else: for j in [0, n-1]: uf.union(m*n, i*n+j, tmp_board, size) for i in range(m): for j in range(n): if not uf.connected(i*n+j, m*n, tmp_board): board[i][j] = 'X'