Surrounded Regions

DFS

Problem

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

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

Thought Process

• Have to use DFS since we are dealing with connected components here. The important part is the connected components that will be using DFS on are the border 'O' and the other 'O' that are connected to them.

• Use DFS on the borders to find all the connected 'O' and initally chage all these connected components to something else to denote the connectivity to the border 'O' (like change them to 'C')

• After all the border DFS is completed, run back through the board and change all 'C' to 'O'. The original 'O' 's that weren't changed to 'C' are the valid regions that can be flipped. So we flip these to 'X'.

Solution

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if len(board) == 0:
            return 
        
        for i in range(len(board)):
            self.dfs(board,i,0)
            self.dfs(board,i,len(board[0])-1)
            
        for j in range(len(board[0])):
            self.dfs(board,0,j)
            self.dfs(board,len(board)-1,j)
            
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'C':
                    board[i][j] = 'O'
                elif board[i][j] == 'O':
                    board[i][j] = 'X'
            
            
    def dfs(self, board, i, j):
        if board[i][j] == 'O':
            
            board[i][j] = 'C'
            if i > 1: self.dfs(board, i-1, j)
            if i+1 < len(board): self.dfs(board, i+1, j)
            if j > 1: self.dfs(board, i, j-1)
            if j+1 < len(board[0]): self.dfs(board, i, j+1)

Time Complexity

• Time: O(m*n)

• Space: O(m*n)