Surrounded Regions

Problem: Surrounded Regions

A brute-force way is to do breadth-first search at each position with "O". If the search end inside the grid surrounded, then we flip these position. However, this kind of search can be quite time-consuming. We can only do BFS at borders with "O" and mark them cannot-be-modified and then mark all other nodes as "X".

Code in Python:

from collections import deque

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
        if len(board) == 1: return

        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in xrange(m)]

        def bfs(r, c):
            queue = deque([(r,c)])
            while queue:
                x, y = queue.popleft()
                board[x][y] = "Z"
                if x > 0 and board[x-1][y] == "O" and not visited[x-1][y]:
                    visited[x-1][y] = True
                    queue.append((x-1, y))
                if x < m-1 and board[x+1][y] == "O" and not visited[x+1][y]:
                    visited[x+1][y] = True
                    queue.append((x+1, y))
                if y > 0 and board[x][y-1] == "O" and not visited[x][y-1]:
                    visited[x][y-1] = True
                    queue.append((x, y-1))
                if y < n-1 and board[x][y+1] == "O" and not visited[x][y+1]:
                    visited[x][y+1] = True
                    queue.append((x, y+1))

        for i in xrange(m):
            if board[i][0] == "O" and not visited[i][0]:
                visited[i][0] = True
                bfs(i, 0)
            if board[i][n-1] == "O" and not visited[i][n-1]:
                visited[i][n-1] = True
                bfs(i, n-1)

        for i in xrange(n):
            if board[0][i] == "O" and not visited[0][i]:
                visited[0][i] = True
                bfs(0, i)
            if board[m-1][i] == "O" and not visited[m-1][i]:
                visited[m-1][i] = True
                bfs(m-1, i)

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

        for i in xrange(m):
            for j in xrange(n):
                if board[i][j] == "Z": board[i][j] = "O"