Python 3 BFS Easy Solution


#1
# we are only considering the borders of A. because any region that
is connected to the border is not to be captured, rest all regions are to 
be captured. So we check all the regions that is connected to the border 
and replace all the other regions with "X".

def bfs(startingarray,A,visited):
    for pos_x,pos_y in startingarray:
        queue = []
        queue.append((pos_x,pos_y))
        visited[pos_x][pos_y] = 1
    
        while queue:
            curr_i,curr_j = queue[0]
            queue.pop(0)
            for pos_i,pos_j in [(0,-1),(-1,0),(0,1),(1,0)]:
                next_i,next_j = (curr_i+pos_i,curr_j+pos_j)
                if (next_i>=0 and next_i<len(A)) and (next_j>=0 and next_j<len(A[0])) and visited[next_i][next_j]==0 and A[next_i][next_j]=="O":
                    queue.append((next_i,next_j))
                    visited[next_i][next_j] = 1
            
class Solution:
    # @param A : list of list of chars
    def solve(self, A):
        visited = [[0]*len(A[0]) for _ in range(len(A))]
        starter = []
        
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] == "O":
                    if i==0 or i==len(A)-1 or j==0 or j==len(A[0])-1:
                        starter.append((i,j))
                
        bfs(starter,A,visited)
    
        #modify A
        for i in range(len(A)):
            for j in range(len(A[0])):
                if visited[i][j] == 1:
                    A[i][j] = "O"
                else:
                    A[i][j] = "X"
    
        return A