Surrounded Regions

此题求的解可以理解为就是围棋中的提子，因为只要连着边界的O就可以不用被改成X，所以实际上我们可以先把四边的所有坐标放进队列中（这里没用真队列而是用的栈，因为这题的顺序无关紧要，而且查重通过修改值避免了），然后对这些坐标进行BFS，把所有和边界联通的O全部改成W以便于我们对死眼和活眼进行区分，在队列中所有的坐标都被BFS过了之后我们再进行一遍检查，把所有为W的坐标改为O，所有为O的坐标改为X即可，同时这里我们也可以发现，任何不需要查重矩阵的BFS，要不本身不关心重复性这个问题，要不就必须通过直接修改矩阵里面的输入为一个特定值，且这个特定值在原矩阵中是不存在的来达到一边遍历一边查重的目的

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        n = len(board)
        if not n:
            return 
        m = len(board[0])
        if not m:
            return 

        stack = [(i, j) for i in xrange(n) for j in xrange(m) if i == 0 or i == n - 1 or j == 0 or j == m - 1]

        while stack:
            row, col = stack.pop()
            if 0 <= row < n and 0 <= col < m and board[row][col] == 'O':
                board[row][col] = 'W'
                for i, j in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                    stack.append((row + i, col + j))

        for i in xrange(n):
            for j in xrange(m):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'W':
                    board[i][j] = 'O'