130. Surrounded Regions

Problem¶

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"|"X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"|"X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an ‘O’ should not be flipped if:

• It is on the border, or
• It is adjacent to an ‘O’ that should not be flipped.
  The bottom ‘O’ is on the border, so it is not flipped.
  The other three ‘O’ form a surrounded region, so they are flipped.

Example 2:

Input: board = [["X"|"X"]]
Output: [["X"|"X"]]

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'.

Solve¶

Simulation using BFS¶

python

Just focus on the rule in the example:

an ‘O’ should not be flipped if:

• It is on the border, or
• It is adjacent to an ‘O’ that should not be flipped.

So I check all the border for 'O'. Adding them all to a queue, and start do a BFS on all of them to find if any Adj cell is also 'O'.

After visiting all 'O' that we should not flip (Which being track with our visited array v), flipping all other remain one.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m = len(board)
        n = len(board[0])
        q = []
        v = set()
        for i in range(n):
            if board[0][i] == 'O':
                q.append((0, i))
            v.add((0, i))
            if board[m - 1][i] == 'O':
                q.append((m - 1, i))
            v.add((m - 1, i))

        for i in range(m):
            if (i,0) not in v:
                if board[i][0]  == 'O':
                    q.append((i, 0))
                v.add((i, 0))
            if (i, n - 1) not in v:
                if board[i][n - 1]  == 'O':
                    q.append((i, n- 1))
                v.add((i, n - 1))

        while len(q) > 0:
            x, y = q.pop(0)
            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
                if not (0 <= nx < m and 0 <= ny < n):
                    continue
                if (nx,ny) in v:
                    continue
                v.add((nx,ny))
                if board[nx][ny] == 'O':
                    q.append((nx,ny))

        for i in range(m):
            for j in range(n):
                if (i, j) not in v:
                    board[i][j] = 'X'