@@ -29,37 +29,38 @@ def dfs(r, c):
2929return islands
3030
3131
32- # BFS Version From Video
32+ # BFS Version From Video
33+ class SolutionBFS :
34+ def numIslands (self ,grid :List [List [str ]])-> int :
35+ if not grid :
36+ return 0
37+
38+ rows ,cols = len (grid ),len (grid [0 ])
39+ visited = set ()
40+ islands = 0
41+
42+ def bfs (r ,c ):
43+ q = deque ()
44+ visited .add ((r ,c ))
45+ q .append ((r ,c ))
46+
47+ while q :
48+ row ,col = q .popleft ()
49+ directions = [[1 ,0 ],[- 1 ,0 ],[0 ,1 ],[0 ,- 1 ]]
50+
51+ for dr ,dc in directions :
52+ r ,c = row + dr ,col + dc
53+ if (r )in range (rows )and (c )in range (cols )and grid [r ][c ]== '1' and (r ,c )not in visited :
54+
55+ q .append ((r ,c ))
56+ visited .add ((r ,c ))
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
3366
34- # def numIslands(self, grid: List[List[str]]) -> int:
35- # if not grid:
36- # return 0
37-
38- # rows, cols = len(grid), len(grid[0])
39- # visited=set()
40- # islands=0
41-
42- # def bfs(r,c):
43- # q = deque()
44- # visited.add((r,c))
45- # q.append((r,c))
46-
47- # while q:
48- # row,col = q.popleft()
49- # directions= [[1,0],[-1,0],[0,1],[0,-1]]
50-
51- # for dr,dc in directions:
52- # r,c = row + dr, col + dc
53- # if (r) in range(rows) and (c) in range(cols) and grid[r][c] == '1' and (r ,c) not in visited:
54-
55- # q.append((r , c ))
56- # visited.add((r, c ))
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