0130-surrounded-regions

Try it on leetcode

Description

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

  • Connect: A cell is connected to adjacent cells horizontally or vertically.
  • Region: To form a region connect every 'O' cell.
  • Surround: A region is surrounded if none of the 'O' cells in that region are on the edge of the board. Such regions are completely enclosed by 'X' cells.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

 

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:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

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(Python)

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])
        def dfs(i, j):
            if  (not(0 <= i <= m-1) or not (0<= j <= n-1) or not board[i][j] == "O"):
                return
            board[i][j] = "#"
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i,j-1)
        
        for i in range(n):
            if board[0][i] == "O":
                dfs(0,i)
            if board[m-1][i] == "O":
                dfs(m-1, i)
        for i in range(m):
            if board[i][0] == "O":
                dfs(i, 0)
            if board[i][n-1] == "O":
                dfs(i, n-1)
        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    board[i][j] = "X"
                elif board[i][j] == "#":
                    board[i][j] = "O"

Dry Run