130. Surrounded Regions

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.

'''
[1] dfs)

idea::
while moving on the border, if meet 'O', then make all connected 'O' as '#'.
after then, remaining 'O' should be flipped (surrounded, so it is not connected border-'O')
and '#' should be 'O' again.

code::
(below)

-T/C: O(m*n)
-S/C: O(m*n)
'''

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        
        m,n=len(board),len(board[0])
        
        # moving over first and last col
        for i in range(m):
            if board[i][0]=="O":
                self.dfs(board,i,0)
            if board[i][n-1]=="O":
                self.dfs(board,i,n-1)
                
        # moving over first and last row
        for i in range(n):
            if board[0][i]=="O":
                self.dfs(board,0,i)
            if board[m-1][i]=="O":
                self.dfs(board,m-1,i)
        
        # flip 
        for i in range(m):
            for j in range(n):
                if board[i][j]=="#":
                    board[i][j]="O"
                elif board[i][j]=="O":
                    board[i][j]="X"
        
    def dfs(self, board, i, j):
        if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j]!="O":
            return
        board[i][j]="#"
        self.dfs(board,i-1,j)
        self.dfs(board,i+1,j)
        self.dfs(board,i,j-1)
        self.dfs(board,i,j+1)