130. Surrounded Regions

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        # edge case
        if not board:
            return 
        row,col = len(board),len(board[0])
        # round1: left right border, find 'O', do dfs
        for i in [0,row-1]:
            for j in range(col):
                if board[i][j] == 'O':
                    self.dfs(i,j,board)
        # round2: top, bottom border
        for i in range(row):
            for j in [0,col-1]:
                if board[i][j] == 'O':
                    self.dfs(i,j,board)
        # whole board loop, find 'O' spot, turn into 'X' 
        #                   find '.'spot, turn into 'O'
        for i in range(row):
            for j in range(col):
                if board[i][j] =='O':
                    board[i][j] = 'X'
                elif board[i][j] == '.':
                    board[i][j] = 'O'
        # dfs: check if i,j out of boundry, if not, turn b[i][j] into '.'
        # go 4 direction dfs 
    def dfs(self,x,y,b):
        if 0<=x<len(b) and 0<=y<len(b[0]) and b[x][y] =='O':
            b[x][y] = '.'
            self.dfs(x+1,y,b)
            self.dfs(x-1,y,b)
            self.dfs(x,y+1,b)
            self.dfs(x,y-1,b)

class UF:
    def __init__(self,bd):

        row = len(bd)
        col = len(bd[0])
        self.parent = ['#'] *(row*col+1)
        for i in range(row):
            for j in range(col):
                # flatten bd[i][j] into 1D
                if bd[i][j] == 'O':
                    idx = i*col + j
                    self.parent[idx] = idx 
        dummy  = row * col
        self.parent[dummy] = dummy
        
    def find(self,x):
         
        while x != self.parent[x]:
            x = self.parent[self.parent[x]]
        return self.parent[x]
    
    def union(self,x,y):
        rtx = self.find(x)
        rty = self.find(y)
        if rtx != rty:
            self.parent[rtx] = rty
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        dir = [[1,0],[-1,0],[0,1],[0,-1]]
        #edge case: no board
        if not board:
            return 
        # initialiez uf
        uf = UF(board)
        row = len(board)
        col = len(board[0])
        dummy = row*col
        # 2 rounds full loop 
        # round1: task I->find 'O's at borde  and connect(flat index ) them together; task II-> for those 'O's that not at the border, unite their 'O' neightbour  together(flat idx)  
        for i in range(row):
            for j in range(col):
                if board[i][j] == 'O':
                    idx_flat = i*col + j
                    if i == 0 or i == row-1 or j ==0 or j == col - 1:
                        uf.union(dummy,idx_flat)
                        continue
                    for di in dir:
                        x = i+di[0]
                        y = j +di[1]
                        # to connect 'O's not connected with border 'O'
                        if 0<=x<row and 0<=y<col and board[x][y] == 'O':
                            idx_f_neighbour = x*col+y
                            uf.union(idx_f_neighbour,idx_flat)
                        
        # go through board again and find 'O', check if they connect with dummy, if not, flip
        for i in range(row):
            for j in range(col):
                if board[i][j] == 'O':
                    idx_flat = i*col + j
                    if uf.find(dummy)!= uf.find(idx_flat):
                        print('flip')
                        board[i][j] = 'X'