 # 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
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)) 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 = [*len(A) for _ in range(len(A))]
starter = []

for i in range(len(A)):
for j in range(len(A)):
if A[i][j] == "O":
if i==0 or i==len(A)-1 or j==0 or j==len(A)-1:
starter.append((i,j))

bfs(starter,A,visited)

#modify A
for i in range(len(A)):
for j in range(len(A)):
if visited[i][j] == 1:
A[i][j] = "O"
else:
A[i][j] = "X"

return A``````