問題描述

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入手郎哭，結果一點思路也沒有，就去網上搜了參考答案僻焚，發(fā)現正確的方法是從O入手。哎叛溢，不應該直接就去搜答案的……是不今天過節(jié)就懶啦旺芽？馋嗜？？
思路：從最邊上一圈的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.