130 Surrounded Regions

https://leetcode.com/problems/surrounded-regions

Python

Fail Try

Did not consider the turns of traversal...

Two cells are connected if they are adjacent cells connected horizontally or vertically.

def solve(self, board: List[List[str]]) -> None:
    for m in range(1, len(board)-1):
        for n in range(1, len(board[m])-1):
            if board[m][n] == 'O':
                left  = next((nx for nx in range(n-1, -1, -1)        if board[m][nx] == 'X'), None)
                right = next((nx for nx in range(n+1, len(board[m])) if board[m][nx] == 'X'), None)
                up    = next((mx for mx in range(m-1, -1, -1)        if board[mx][n] == 'X'), None)
                down  = next((mx for mx in range(m+1, len(board))    if board[mx][n] == 'X'), None)


                # print(f"[{m}, {n}] {left} {right} {up} {down}")
                if left  is not None and  \
                   right is not None and \
                   up    is not None and \
                   down  is not None:
                    board[m][n] = 'X'

Second Try (Not Correct)

Start from edge and determine by DFS alg

def solve(self, board: List[List[str]]) -> None:
    for m in range(1, len(board)-1):
        for n in range(1, len(board[m])-1):
            if board[m][n] == 'O':
                left  =  next((
                    nx for nx in range(n-1, -1, -1)
                    if board[m][nx] == 'X'),
                    None
                )
                right = next((
                    nx for nx in range(n+1, len(board[m]))
                    if board[m][nx] == 'X'),
                    None
                 )
                up = next((
                    mx for mx in range(m-1, -1, -1)
                    if board[mx][n] == 'X'),
                    None
                )
                bottom = next((
                    mx for mx in range(m+1, len(board))
                    if board[mx][n] == 'X'),
                    None
                )

                if left is not None and right is not None and up is not None and bottom is not None:
                    board[m][n] = 'X'