# Python BFS

• ``````    # 1. read the length and width
if len(grid) == 0:
return 0
(m,n) = (len(grid),len(grid[0]))
if (m == 0) or (n == 0):
return 0
# 2. Create a Visit matrix for checking
visit = [[False for j in range(n)] for i in range(m)]
count_island = 0

def check(x, y):
if x >=0 and x <m and y>=0 and y <n and visit[x][y] == False and grid[x][y] == "1":
return True
def bfs(x,y):
# move to up, down, right, left

moves = [(0,1),(0,-1),(1,0),(-1,0)]

q = [(x,y)]
while q:
x = q[0][0]
y = q[0][1]
q.pop(0)

for dx, dy in moves:
newx = x + dx
newy = y + dy
if check(newx, newy):
visit[newx][newy] = True
q.append((newx,newy))

# 3. for loop for each components
for row in range(m):
for col in range(n):
# 3.1 Check it is in the Matrix
if check (row, col):
# 3.2 Mark as visit for saving time
visit[row][col] = True
# 3.3 BFS for each node
bfs(row,col)
# 3.4 count +=1
count_island += 1
return count_island``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.