https://oj.leetcode.com/problems/surrounded-regions/

xo.py

class Solution:
    # @param board, a 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, b):
        if len(b) == 0:
            return []
        board = [list(x) for x in b]
        allEntrances = self.findAllEntrances(board)
        
        if len(allEntrances) == 0:
            return self.output(board, [])

        stack = allEntrances

        queue = []

        while True:
            node = stack.pop()

            adjacentNodes = self.getAdjacentNodes(board, node)

            queue.append(node)

            for n in adjacentNodes: 
                if n in queue:
                    continue
                stack.append(n)

            if len(stack) == 0:
                break;

        return self.output(board, queue)


    def findAllEntrances(self, board):
        width = len(board)
        height = len(board[0])

        entrances = []

        for i in range(width):
            if board[i][0] == 'O':
                entrances.append((i, 0))
        
        for i in range(width):
            if board[i][height - 1] == 'O':
                entrances.append((i, height - 1))

        for i in range(height):
            if board[0][i] == 'O':
                entrances.append((0, i))
        
        for i in range(height):
            if board[width - 1][i] == 'O':
                entrances.append((width - 1, i))

        return entrances

    def output(self, board, nodes):
        w, h = len(board), len(board[0])

        for r in range(w):
            for c in range(h):
                board[r][c] = 'X'

        for n in nodes:
            board[n[0]][n[1]] = 'O'

        ret = []
        for i in range(len(board)):
            ret.append(''.join(board[i]))

        return ret

    def getAdjacentNodes(self, board, node):
        width = len(board)
        height = len(board[0])

        up = (node[0] - 1, node[1])
        down = (node[0] + 1, node[1])
        left = (node[0], node[1] - 1)
        right = (node[0], node[1] + 1)

        ret = []

        for n in (up, down, left, right):
            w, h = n
            if w < width and w >= 0 and h < height and h >= 0:
                if board[n[0]][n[1]] == 'O':
                    ret.append(n)
        return ret
        
        
        
s = Solution()
b = ["OXXOX",  "XOOXO", "XOXOX", "OXOOO", "XXOXO"]


print s.solve(b)