0200-number-of-islands.py

classSolution:
defnumIslands(self, grid: List[List[str]]) ->int:
ifnotgridornotgrid[0]:
return0

islands=0
visit=set()
rows, cols=len(grid), len(grid[0])

defdfs(r, c):
if (
rnotinrange(rows)
orcnotinrange(cols)
orgrid[r][c] =="0"
or (r, c) invisit
 ):
return

visit.add((r, c))
directions= [[0, 1], [0, -1], [1, 0], [-1, 0]]
fordr, dcindirections:
dfs(r+dr, c+dc)

forrinrange(rows):
forcinrange(cols):
ifgrid[r][c] =="1"and (r, c) notinvisit:
islands+=1
dfs(r, c)
returnislands


# BFS Version From Video
classSolutionBFS:
defnumIslands(self, grid: List[List[str]]) ->int:
ifnotgrid:
return0

rows, cols=len(grid), len(grid[0])
visited=set()
islands=0

defbfs(r,c):
q=deque()
visited.add((r,c))
q.append((r,c))

whileq:
row,col=q.popleft()
directions= [[1,0],[-1,0],[0,1],[0,-1]]

fordr,dcindirections:
r,c=row+dr, col+dc
if (r) inrange(rows) and (c) inrange(cols) andgrid[r][c] =='1'and (r ,c) notinvisited:

q.append((r , c ))
visited.add((r, c ))

forrinrange(rows):
forcinrange(cols):

ifgrid[r][c] =="1"and (r,c) notinvisited:
bfs(r,c)
islands+=1

returnislands