130. Surrounded Regions

import collections 
class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
    
        if not board:
            return 
        
        queue=collections.deque([])
        #number of rows 
        m=len(board)
        #number of columns 
        n=len(board[0])
        #put the edge elements into queue
        for i in xrange(m): 
            queue.append((i,0))
            queue.append((i,n-1))
        for j in xrange(n):
            queue.append((0,j))
            queue.append((m-1,j))
        #examine each edge elements , mark each edge 'O' as 'V' and check its adjacent elements
        while queue:
            i,j=queue.popleft()
            if board[i][j] in ['O','V']:
                board[i][j]='V'
                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if x>=0 and x<m and y>=0 and y<n and board[x][y]=='O':
                        board[x][y]='V'
                        queue.append((x,y))
        #leave all marked 'V' as 'O', flip all other 'O' 
        for i in xrange(m):
            for j in xrange(n):
                if board[i][j]!='V':
                    board[i][j]='X'
                else:
                    board[i][j]='O'