Skip to content

130. Surrounded Regions

Difficulty Topics

Description

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"]]
Output: [["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"]]
Output: [["X"]]

 

Constraints:

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

Solution

surrounded-regions.py
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows, cols = len(board), len(board[0])
        queue = collections.deque()

        for x in range(rows):
            for y in [0, cols - 1]:
                if board[x][y] == 'O':
                    board[x][y] = 'G'
                    queue.append((x, y))

        for x in [0, rows - 1]:
            for y in range(cols):
                if board[x][y] == 'O':
                    board[x][y] = 'G'
                    queue.append((x, y))

        while queue:
            x, y = queue.popleft()

            for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if 0 <= dx < rows and 0 <= dy < cols and board[dx][dy] == 'O':
                    board[dx][dy] = 'G'
                    queue.append((dx, dy))

        for x in range(rows):
            for y in range(cols):
                if board[x][y] == 'O':
                    board[x][y] = 'X'
                elif board[x][y] == 'G':
                    board[x][y] = 'O'