Commitac8a900

authored

Adding BFS For Convenience

1 parent2c47cad commitac8a900Copy full SHA for ac8a900

File tree

+36

-0

lines changed

+36

-0

lines changed

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -27,3 +27,39 @@ def dfs(r, c):`
`27`	`27`	`islands+=1`
`28`	`28`	`dfs(r,c)`
`29`	`29`	`returnislands`
	`30`	`+`
	`31`	`+defnumIslands(self,grid:List[List[str]])->int:`
	`32`	`+ifnotgrid:`
	`33`	`+return0`
	`34`	`+`
	`35`	`+rows,cols=len(grid),len(grid[0])`
	`36`	`+visited=set()`
	`37`	`+islands=0`
	`38`	`+`
	`39`	`+# BFS Version From Video`
	`40`	`+`
	`41`	`+# def bfs(r,c):`
	`42`	`+# q = deque()`
	`43`	`+# visited.add((r,c))`
	`44`	`+# q.append((r,c))`
	`45`	`+`
	`46`	`+# while q:`
	`47`	`+# row,col = q.popleft()`
	`48`	`+# directions= [[1,0],[-1,0],[0,1],[0,-1]]`
	`49`	`+`
	`50`	`+# for dr,dc in directions:`
	`51`	`+# r,c = row + dr, col + dc`
	`52`	`+# if (r) in range(rows) and (c) in range(cols) and grid[r][c] == '1' and (r ,c) not in visited:`
	`53`	`+`
	`54`	`+# q.append((r , c ))`
	`55`	`+# visited.add((r, c ))`
	`56`	`+`
	`57`	`+`
	`58`	`+# for r in range(rows):`
	`59`	`+# for c in range(cols):`
	`60`	`+`
	`61`	`+# if grid[r][c] == "1" and (r,c) not in visited:`
	`62`	`+# bfs(r,c)`
	`63`	`+# islands +=1`
	`64`	`+`
	`65`	`+# return islands`

Comments

(0)