https://leetcode.com/problems/number-of-islands/
## タグ
## 概要
> Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and `'0'`s (water), return _the number of islands_.
>
> An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
## 方針
### Intuition
グラフの問題。訪れた場所を管理してlandの間は再帰的に見ていくのが良い。
### DFS
Time Complexity: $O(mn)$
Space Complexity: $O(mn)$
Where: `m = len(grid), n = len(grid[0])`
```python
def numIslands(self, grid: List[List[str]]) -> int:
# 手当たり次第に左上から島を探します。
# 未発見のland("1")に遭遇したら島に上陸します
# 島を上下左右に移動して訪れたことを記録します
# また次の島を探します（以下同じことの繰り返し）
def mark_as_visited(row: int, col: int) -> None:
if not (0 <= row < m and 0 <= col < n):
return
if grid[row][col] == "0":
return
# mark as visited
grid[row][col] = "0"
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in dirs:
mark_as_visited(row + dr, col + dc)
m, n = len(grid), len(grid[0])
num_of_islands = 0
for row in range(m):
for col in range(n):
if grid[row][col] == "1":
num_of_islands += 1
mark_as_visited(row, col)
return num_of_islands
```