130. Surrounded Regions

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.

My Answer 1: Accepted (Runtime: 144 ms - 45.51% / Memory Usage: 16.3 MB - 35.77%)

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if len(board) != 0:
            R = len(board)
            C = len(board[0])

            def isIsland(i, j):
                board[i][j] = 'P'

                if i-1 >= 0 and board[i-1][j] == 'O':
                    isIsland(i-1, j)
                if i+1 < R and board[i+1][j] == 'O':
                    isIsland(i+1, j)
                if j-1 >= 0 and board[i][j-1] == 'O':
                    isIsland(i, j-1)
                if j+1 < C and board[i][j+1] == 'O':
                    isIsland(i, j+1)

            for i in range(0, R):
                if i == 0 or i == R-1:
                    for j in range(0, C):
                        if board[i][j] == 'O':
                            board[i][j] = 'P'
                            isIsland(i, j)
                else:
                    if board[i][0] == 'O':
                        j = 0
                        isIsland(i, j)
                    if board[i][C-1] == 'O':
                        j = C-1
                        isIsland(i, j)
            
            for i in range(0, R):
                for j in range(0, C):
                    if board[i][j] == 'P':
                        board[i][j] = 'O'
                    elif board[i][j] == 'O':
                        board[i][j] = 'X'

200. Number of Islands 를 각색해봤읍니다

1. border 와 연결된 island 들을 모두 P 로 바꾸기 (O 로 살아남을 애들)
2. 남은 O 들은 X 로 바꿔줌
3. P 들은 다시 O 로 바꿔줌

BFS

Solution 1: Runtime: 144 ms - 45.51% / Memory Usage: 15.5 MB - 85.39%

class Solution:
    '''
    Time complexity : O(MXN)
    Space complexity : O(1)

    First, check the four border of the matrix. If there is a element is
    'O', alter it and all its neighbor 'O' elements to 'N'.

    Then ,alter all the 'O' to 'X'

    At last,alter all the 'N' to 'O'

    example: 

    X X X X           X X X X             X X X X
    X X O X  ->       X X O X    ->       X X X X
    X O X X           X N X X             X O X X
    X O X X           X N X X             X O X X

    '''
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return
        R, C = len(board), len(board[0])
        if R <= 2 or C <= 2:
            return
        
        # queue for bfs
        q = deque()
        
        # start from the boarder and replace all O to N
        # put all the boarder value into queue.
        for r in range(R):
            q.append((r, 0))
            q.append((r, C-1))

        for c in range(C):
            q.append((0, c))
            q.append((R-1, c))
        
        while q:
            r, c = q.popleft()
            if 0<=r<R and 0<=c<C and board[r][c] == "O":
                # modify the value from O to N
                board[r][c] = "N"
                # append the surrouding cells to queue.
                q.append((r, c+1))
                q.append((r, c-1))
                q.append((r-1, c))
                q.append((r+1, c))
        
        # replace all the O to X, then replace all the N to O
        for r in range(R):
            for c in range(C):
                if board[r][c] == "O":
                    board[r][c] = "X"
                if board[r][c] == "N":
                    board[r][c] = "O"

deque 를 사용하지만 N 으로 바꿔주는게 내거랑 비슷한듯