题目链接

题目原文

Given a 2D board containing 'X' and '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

题目大意

给出一个铺满O或者X的区域，将被X围住的O都换成X

解题思路

使用BFS从边上开始搜索，如果是'O'，那么搜索'O'周围的元素，并将'O'置换为'D'，这样每条边都DFS或者BFS一遍。而内部的'O'是不会改变的。这样下来，没有被围住的'O'全都被置换成了'D'，被围住的'O'还是'O'，没有改变。然后遍历一遍，将'O'置换为'X'，将'D'置换为'O'。

代码

class Solution(object):    def solve(self, board):        """        :type board: List[List[str]]        :rtype: void Do not return anything, modify board in-place instead.        """        def fill(x, y):            if x < 0 or x > m - 1 or y < 0 or y > n - 1 or board[x][y] != 'O':                return            queue.append((x, y))            board[x][y] = 'D'        def bfs(x, y):            if board[x][y] == 'O':                fill(x, y)            while queue:                cur = queue.pop(0)                i = cur[0]                j = cur[1]                fill(i + 1, j)                fill(i - 1, j)                fill(i, j + 1)                fill(i, j - 1)        if len(board) == 0:            return        m = len(board)        n = len(board[0])        queue = []        for i in range(n):            bfs(0, i)            bfs(m - 1, i)        for j in range(1, m - 1):            bfs(j, 0)            bfs(j, n - 1)        for i in range(m):            for j in range(n):                if board[i][j] == 'D':                    board[i][j] = 'O'                elif board[i][j] == 'O':                    board[i][j] = 'X'