# 200. Number of Islands
#### Difficulty: Medium
link: https://leetcode.com/problems/number-of-islands/

這題用BFS或DFS都行，為了避免重複計算島嶼，每當拜訪到一個新的島嶼，也要把同個島嶼的cells通通標記已拜訪。

有個小技巧，grid拜訪過的cell就改成"#"，這樣就不需要額外的空間來做紀錄。

### 1. BFS
#### $O(mn)$ runtime, $O(mn)$ space

##### python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def bfs(i, j):
            grid[i][j] = "#"
            queue = deque([[i, j]])
            while queue:
                x, y = queue.popleft()
                for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
                        grid[nx][ny] = "#"
                        queue.append([nx, ny])
        
        island = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    island += 1
                    bfs(i, j)
        
        return island

### 2. DFS
#### $O(mn)$ runtime, $O(mn)$ space

##### python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j] == "1":
                grid[i][j] = "#"
                dfs(i-1, j)
                dfs(i+1, j)
                dfs(i, j-1)
                dfs(i, j+1)
        
        island = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    island += 1
                    dfs(i, j)
        
        return island

###### tags: `leetcode`