# 資訊

:::info
- Question: 200. Number of Islands
- From: Leetcode Daily Challenge 2024.04.19
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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.

> Example 1:
:::success
* Input: `grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]`
* Output: 1
:::

> Example 2:
:::success
* Input: `grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]`
* Output: 3
:::

> Constraints:
:::success
* `m` == `grid.length`
* `n` == `grid[i].length`
* 1 <= `m`, `n` <= 300
* `grid[i][j]` is `'0'` or `'1'`.
:::

---

# 解法

## 概念

一樣是 matrix 結合 DFS，判斷 island 的方法是看跟左邊和上面是否相連，有就加入那個 set，沒有就創造一個 set，不過要注意有需要把兩個 sets 做 union 的情況，這時候要把其中一塊 pop 掉

## 程式碼

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        sets = []
        ans = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    flag = 1
                    kk = 0
                    if i > 0 and grid[i-1][j] == '1':
                        for k in range(ans):
                            if (i-1,j) in sets[k]:
                                sets[k] = sets[k].union( {(i,j)} )
                                kk = k
                                flag = 0
                                break
                    if j > 0 and grid[i][j-1] == '1':
                        for k in range(ans):
                            if (i,j-1) in sets[k]:
                                sets[k] = sets[k].union( {(i,j)} )
                                if flag == 0:
                                    sets[k] = sets[k].union( sets[kk] )
                                    if k != kk:
                                        sets.pop(kk)
                                        ans -= 1
                                else:
                                    flag = 0
                                break
                    if flag:
                        new = { (i,j) }
                        sets.append(new)
                        ans += 1
        return ans

---

# 複雜度

## 時間複雜度

走過 matrix 所以是 $O(mn)$


## 空間複雜度

儲存 set，所以最差也是 $O(mn)$