| 50 | # BFS Version From Video |
| 51 | class SolutionBFS: |
| 52 | def numIslands(self, grid: List[List[str]]) -> int: |
| 53 | if not grid: |
| 54 | return 0 |
| 55 | |
| 56 | rows, cols = len(grid), len(grid[0]) |
| 57 | visited = set() |
| 58 | islands = 0 |
| 59 | |
| 60 | def bfs(r, c): |
| 61 | q = deque() |
| 62 | visited.add((r, c)) |
| 63 | q.append((r, c)) |
| 64 | |
| 65 | while q: |
| 66 | row, col = q.popleft() |
| 67 | directions = [[1, 0],[-1, 0],[0, 1],[0, -1]] |
| 68 | |
| 69 | for dr, dc in directions: |
| 70 | r, c = row + dr, col + dc |
| 71 | if (r) in range(rows) and (c) in range(cols) and grid[r][c] == '1' and (r, c) not in visited: |
| 72 | |
| 73 | q.append((r, c )) |
| 74 | visited.add((r, c )) |
| 75 | |
| 76 | for r in range(rows): |
| 77 | for c in range(cols): |
| 78 | |
| 79 | if grid[r][c] == "1" and (r, c) not in visited: |
| 80 | bfs(r, c) |
| 81 | islands += 1 |
| 82 | |
| 83 | return islands |
| 84 | |