问题描述

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

问题分析

看到题目我就想怎么能画出一个封闭圈，想从X入手，结果一点思路也没有，就去网上搜了参考答案，发现正确的方法是从O入手。哎，不应该直接就去搜答案的……是不今天过节就懒啦？？？
思路：从最边上一圈的O入手，能从O到达的O都是没有被包围的，不能从最边上一圈的O到达的O就是被包围起来的O，用BFS搜索。

AC代码

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        row = len(board)
        if row <= 2:
            return
        column = len(board[0])
        if column <= 2:
            return
        mark = [[0 for i in range(column)] for j in range(row)]
        for i in range(row):
            if i == 0 or i == row-1:
                for j in range(column):
                    if board[i][j] == 'O':
                        mark[i][j] = 1
                        self.bfs(i, j, board, mark)
            else:
                if board[i][0] == 'O':
                    mark[i][0] = 1
                    self.bfs(i, 0, board, mark)
                if board[i][column-1] == 'O':
                    mark[i][column-1] = 1
                    self.bfs(i, column-1, board, mark)
        for i in range(row):
            for j in range(column):
                if board[i][j] == 'O' and mark[i][j] == 0:
                    board[i][j] = 'X'

    def bfs(self, i, j ,board, mark):
        n = len(board)
        m = len(board[0])
        stack = [(i, j)]
        while len(stack) != 0:
            p, q = stack.pop(0)
            if p-1 > 0 and board[p-1][q] == 'O' and mark[p-1][q] == 0:
                mark[p-1][q] = 1
                stack.append((p-1, q))
            if q-1 > 0 and board[p][q-1] == 'O' and mark[p][q-1] == 0:
                mark[p][q-1] = 1
                stack.append((p, q-1))
            if p+1 < n-1 and board[p+1][q] == 'O' and mark[p+1][q] == 0:
                mark[p+1][q] = 1
                stack.append((p+1, q))
            if q+1 < m-1 and board[p][q+1] == 'O' and mark[p][q+1] == 0:
                mark[p][q+1] = 1
                stack.append((p, q+1))

Runtime: 172 ms, which beats 63.30% of Python submissions.