List 130. Surrounded Regions leetcode solution using bfs 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.


Input:

X X X X
X O O X
X X O X
X O X X


Output:

X X X X
X X X X
X X X X
X O X X


All I am doing is to traverse all the edges and set all of them to x_not_possible and also there connected neighbors. Connected neighbors are found by doing bfs.

Traverse once more and set x_not_possible back to O and all the nodes not set to x_not_possible to X.

Code:

class Solution(object):
    def solve(self, board):
        if not board:
            return

        row_len, col_len = (len(board), len(board[0]))
        if row_len == 1 and col_len == 1:
            return

        def get_neighbours((i, j)):
            directions = []
            map_direction = {"left":(0, -1), "right":(0, 1), "up":(-1, 0), "down":(1, 0)}
            for _i, _j in map_direction.values():
                __i, __j = _i + i, _j + j
                if __i &lt; row_len and __i &gt;= 0 and __j &lt; col_len and __j &gt;= 0:
                    yield __i, __j

        increment_col, decrement_row, decrement_col, increment_row = (False, False, False, True)
        queue = []
        stop = [0, 0]
        while True:
            row, col = 0, 1
            if increment_row:
                if stop[row] + 1 &gt;= row_len:
                    increment_col, increment_row = True, False
                    continue
                else:
                    stop[row] += 1
            elif increment_col:
                if stop[col] + 1 &gt;= col_len:
                    decrement_row, increment_col = True, False
                    continue
                else:
                    stop[col] += 1
            elif decrement_row:
                if stop[row] - 1 &lt; 0:
                    decrement_col, decrement_row = True, False
                    continue
                else:
                    stop[row] -= 1
            elif decrement_col:
                if stop[col] - 1 &lt; 0:
                    break
                else:
                    stop[col] -= 1
            i, j = stop
            if board[i][j] == "O":
                queue.append((i, j))

        while len(queue):
            i, j = queue.pop()
            board[i][j] = "x_not_possible"
            for k, l in get_neighbours((i, j)):
                if board[k][l] == "O":
                    board[k][l] = "x_not_possible"
                    queue.append((k, l))

        for i in range(row_len):
            for j in range(col_len):
                if board[i][j] == "O":
                    board[i][j] = 'X'
                elif board[i][j] == "x_not_possible":
                    board[i][j] = 'O'
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))