130. Surrounded Regions

class Solution:
    def solve(self, M: List[List[str]]) -> None:
        m, n = len(M), len(M[0])
        offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def neighbors(y: int, x: int) -> Iterator[Tuple[int, int]]:
            for dy, dx in offsets:
                ny, nx = y + dy, x + dx
                if 0 <= ny < m and 0 <= nx < n and M[ny][nx] == "O":
                    yield (ny, nx)

        def dft(i: int, j: int) -> None:
            M[i][j] = "#"
            for ii, jj in neighbors(i, j):
                dft(ii, jj)

        def edges() -> Iterator[Tuple[int, int]]:
            for i in range(m):
                yield (i, 0)
                yield (i, n - 1)

            for j in range(n):
                yield (0, j)
                yield (m - 1, j)

        for i, j in edges():
            if M[i][j] == "O":
                dft(i, j)

        for i in range(m):
            for j in range(n):
                if M[i][j] == "O":
                    M[i][j] = "X"
                elif M[i][j] == "#":
                    M[i][j] = "O"