LC 130 - Surrounded Regions

Question

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: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

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'.

Links

Question here and solution here

Solution

concept

This question is very similar to [[417. Pacific Atlantic Water Flow]] in the sense we have to think reverse and start from the boarders. The key idea is to start DFS from the O on the edges and try to see any other O is connected to it. Since any O connected to the edges cannot be captured, we can mark these impossible O as # first. We then go through the grid again and

1. turn any remaining O into X since they can be captured
2. turn # back to O since they cannot be captured

code

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])
        directions = [[0,1],[1,0],[0,-1],[-1,0]]

        def dfs(r, c):
            if (r < 0 or r >= ROWS or
                c < 0 or c >= COLS or
                board[r][c] in ["X", "#"]):
                return

            board[r][c] = "#"
            for dr, dc in directions:
                dfs(r + dr, c + dc)
                
		# only the edges
        for r in range(ROWS):
            if board[r][0] == "O":
                dfs(r, 0)
            if board[r][COLS - 1] == "O":
                dfs(r, COLS - 1)
        for c in range(COLS):
            if board[0][c] == "O":
                dfs(0, c)
            if board[ROWS - 1][c] == "O":
                dfs(ROWS - 1, c)
                
		# turn the board again
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"
                if board[r][c] == "#":
                    board[r][c] = "O"
                    
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        
        with a visited set
        this is the same as above since if we start from the edges, visited is guaranteed to be captured with mark '#'
        """
        ROWS, COLS = len(board), len(board[0])
        visited = set()
        directions = [[0,1],[1,0],[0,-1],[-1,0]]

        def dfs(r,c):
            if (r < 0 or r >= ROWS or
                c < 0 or c >= COLS or
                (r,c) in visited or board[r][c] == "X"):
                return
            
            visited.add((r,c))
            board[r][c] = "F"
            for dr, dc in directions:
                dfs(r + dr, c + dc)
        
        # from 4 edges
        for r in range(ROWS):
            dfs(r, 0)
            dfs(r, COLS - 1)
        for c in range(COLS):
            dfs(0, c)
            dfs(ROWS - 1, c)

        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"
                if board[r][c] == "F":
                    board[r][c] = "O"

Complexity

time: $O(mn)$
space: $O(mn)$