Commit4ef8de4

authored

Merge pull requestneetcode-gh#1038 from Mark-777-0/patch-1

Adding BFS For Convenience

2 parents825a25b +72ac563 commit4ef8de4Copy full SHA for 4ef8de4

File tree

+37

-0

lines changed

+37

-0

lines changed

Lines changed: 37 additions & 0 deletions

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

Comments

(0)