首頁

# Leetcode 封閉島嶼解題

No. 1254. Number of Closed Islands

# 題目

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

# 題目翻譯

給定一個由一堆 0（土地）和一堆 1（水）組成的二維陣列。 一個島是一個最大的 4 方向連接 0 的組合，一個封閉的島是一個完全（所有左、上、右、下）被 1 包圍的島。

返回封閉島嶼的數量。

# 解題思路

# 解題思路 1

根據題目所述，土地 0 的周圍需要被 水 1 包圍才算島嶼，那在陣列邊界的 土地 0 都不可能被認列成島嶼。

所以可以想到 當陣列走訪到 x index = 0 or len (grid)-1 的 土地都要當作不可用土地 (y index 同理)

# 解題思路 2

由於題目要計算島嶼數量，所以 相鄰的土地要被一同認列為同一座島嶼不可重複認列

所以可以想到當走訪過該土地時為了避免重複計算，需要將走訪過的土地進行標記

# 解題思路 3

相鄰土地當錯同一島嶼土地由於是使用 2D 陣列

可以讓 grid [x][y] 的索引值 ±1 達到走訪效果

# 參考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def dfs(self, i: int, j: int, grid) -> None:# 走訪鄰近土地或海洋
        m, n = len(grid), len(grid[0])
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 0:
            return
        grid[i][j] = 1
        self.dfs(i+1, j, grid)
        self.dfs(i-1, j, grid)
        self.dfs(i, j+1, grid)
        self.dfs(i, j-1, grid)

    def closedIsland(self, grid) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if (i*j==0 or i==m-1 or j==n-1) and (grid[i][j]==0): # 清除邊界
                    self.dfs(i, j, grid)
        for i in range(m):
            for j in range(n):
                print(grid[i][j], end=' ')#查看清除邊界後的樣貌 無實質作用
            print()
        count = 0
        for i in range(1, m-1):
            for j in range(1, n-1):
                if grid[i][j] == 0:# 計算島嶼
                    self.dfs(i, j, grid)
                    count += 1
        return count
    

s = Solution()
print(s.closedIsland(
    grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
))
print(s.closedIsland(
    grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
))

# 參考答案解析

# 解析 1

走訪 2D 陣列 且將邊界的 0 進行清除 使用 dfs 函式順便清除連接邊界的其他土地 0

1
2
3
4
for i in range(m):
    for j in range(n):
        if (i*j==0 or i==m-1 or j==n-1) and (grid[i][j]==0): #Clean Border
            self.dfs(i, j, grid)

# 解析 2

被走訪的陣列值設置成走訪過了 (1) 且尋找該位址的鄰近 (上下左右) 是否也是土地
，由於使用 i,j 控制要走訪的索引所以在走訪過程也要注意是否索引值不合理 如超出邊界

1
2
3
4
5
6
7
8
9
def dfs(self, i: int, j: int, grid) -> None:
    m, n = len(grid), len(grid[0])
    if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 0:
        return
    grid[i][j] = 1
    self.dfs(i+1, j, grid)# 向右走訪
    self.dfs(i-1, j, grid)# 向左走訪
    self.dfs(i, j+1, grid)# 向上走訪
    self.dfs(i, j-1, grid)# 向下走訪

# 解析 3

由於先前將邊界及其相鄰土地清除，所以剩下的土地都是島嶼，為避免重複計算也使用 dfs 將走訪過的土地進行標記，且當偵測到有土地時將島嶼計算數量 count + 1

1
2
3
4
5
6
7
8
count = 0
for i in range(1, m-1):
    for j in range(1, n-1):
        if grid[i][j] == 0:# Calculate the number of islands
            self.dfs(i, j, grid)
            count += 1
return count

# 變化題

Leetcode 1020. Number of Enclaves
Leetcode 200. Number of Islands
Leetcode 130. Surrounded Regions
Leetcode 695. Max Area of Island
Leetcode 463. Island Perimeter
Leetcode 1727. Largest Submatrix With Rearrangements

計算封閉土地