LeetCode 130 - Surrounded Regions - 2022.12.27 solution

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        How to solve it:
        - The only way for a region to not be surrounded is if it is connected
        to the edge of the board.  So we're going to run DFS from the edges of the
        board to switch those regions to a temporary value, then iterate through
        every cell to switch the remaining "O" cells to "X", and then iterate again
        to switch the intermediate values back to "O".
        """
        ROWS = len(board)
        COLS = len(board[0]) if ROWS else 0

        # Switch the regions connected to the edge to a temporary value

        top_edge = set([(0, i) for i in range(COLS)])
        left_edge = set([(i, 0) for i in range(ROWS)])
        right_edge = set([(i, COLS - 1) for i in range(ROWS)])
        bottom_edge = set([(ROWS - 1, i) for i in range(COLS)])

        handled_positions = set()

        def flip_o_neighbors(pos):
            adjustments = [
                [0, 1],
                [0, -1],
                [1, 0],
                [-1, 0],
            ]
            neighbors = [(a[0] + pos[0], a[1] + pos[1]) for a in adjustments]
            for neighbor in neighbors:
                if neighbor[0] < 0 or neighbor[0] > ROWS - 1 or \
                   neighbor[1] < 0 or neighbor[1] > COLS - 1:
                   continue
                if board[neighbor[0]][neighbor[1]] == 'O':
                    board[neighbor[0]][neighbor[1]] = 'T'
                    handled_positions.add(neighbor)
                    flip_o_neighbors(neighbor)

        for position in top_edge.union(left_edge).union(right_edge).union(bottom_edge):
            if position not in handled_positions:
                if board[position[0]][position[1]] == 'O':
                    board[position[0]][position[1]] = 'T'
                    handled_positions.add(position)
                    flip_o_neighbors(position)


        # Switch the remaining "O" cells to "X"
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == 'O':
                    board[r][c] = 'X'

        # Switch the intermediate values back to "O"
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == 'T':
                    board[r][c] = 'O'

        return board