List 130. Surrounded Regions leetcode solution using bfs
Review

There are a few things that could be improved upon.

1 .Your get_neighbours could use some love 

map_direction = {"left":(0, -1), "right":(0, 1), "up":(-1, 0), "down":(1, 0)} 

I might understand using a dictionary so you can see which value corresponds to which direction, but this may be simplified to just using a tuple of directions.

_i and __i are variables badly named I believe, maybe new_i or something would be better. _i and __i implies that these variables are private/protected, and in your case they are not.

Secondly I think with this:

increment_col, decrement_row, decrement_col, increment_row = (False, False, False, True)

You reinvent your get_neighbours

2. Use enumerate

I think this was said in your last question you posted on CR too, and it is still valid. You should defenitly use enumerate when possible, see the corresponding PEP article

3. Doing this in one loop

You have:


A while True: loop
Another while loop


This could be done in one loop, by tracking if any of the current visited vertex in the dfs, are in either the last or first (row or collumn)

Alternative code

def get_neighbours(board, position):
    directions = ((0, -1), (0, 1), (-1, 0), (1, 0))
    for direction in directions:
        new_x, new_y = (p+d for d, p in zip(direction, position))
        if new_x in range(0, len(board) - 1) and new_y in range(0, len(board[0]) - 1):
            yield new_x, new_y

def dfs(board, start):
    visited, stack = set(), [start]
    change = True

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            if change and (vertex[0] in (0, len(board) - 1) or vertex[1] in (0, len(board[0]) - 1)):
                change = False                
            visited.add(vertex)
            for x, y in get_neighbours(board, vertex):
                if (x, y) not in visited  and board[x][y] == "O":
                    stack.append((x, y))
    return visited, change

def solve(board):
    visited = set()

    # Group the O's
    for x, row in enumerate(board):
        for y, col in enumerate(row):
            if col == 'O' and (x, y) not in visited:
                group, change = dfs(board, (x, y))
                visited |= group
                if change:
                    for o in group:
                        board[o[0]][o[1]] = "X"

    return board

if __name__ == '__main__':
    board = [["X", "X", "X", "X"],
             ["X", "O", "O", "X"],
             ["X", "X", "O", "X"],
             ["X", "O", "X", "X"]]
    print(solve(board))