吐司寫LeetCode :1905. Count Sub Islands

吐司寫LeetCode :1905. Count Sub Islands

Toast_1001 Lv1
  2024-08-28 22:58:21 2024-08-28 22:58:21 撰寫   2024-09-06 02:39:08 2024-09-06 02:39:08 更新    1.9k 字數  8 分鐘  

topic: dfs bfs matrix

題目原文

題目連結: 點我

You are given two m x n binary matrices grid1 and grid2 containing only 0‘s (representing water) and 1‘s (representing land). An island is a group of 1‘s connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

Example 1:

Input:
grid1 = [[1, 1, 1, 0, 0], [0, 1, 1, 1, 1], [0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1]],
grid2 = [[1, 1, 1, 0, 0], [0, 0, 1, 1, 1], [0, 1, 0, 0, 0], [1, 0, 1, 1, 0], [0, 1, 0, 1, 0]]
Output:
3
Explanation:
In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

Example 2:

Input:
grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]],
grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Output:
2
Explanation:
In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

Constraints:

  • m == grid1.length == grid2.length
  • n == grid1[i].length == grid2[i].length
  • 1 <= m, n <= 500
  • grid1[i][j] and grid2[i][j] are either 0 or 1.

題解

題目中給我們兩張一樣大的地圖分別為 grid1 與 grid2，兩張地圖由 0 和 1 組成，分別代表海洋與陸地，因此可從兩張地圖中看出島嶼的位置。

若在 grid2 上的某座島嶼對應到 grid1 上時，整座島嶼都位於 grid1 中的一座島嶼上，則可稱位於grid2的該島嶼為子島嶼(Sub-island) 。本題想要我們找出在 grid2 上的所有子島嶼。

想一想

本題的邊長上限不大（最大地圖為500*500），基本上可以用基本的 深度優先搜尋（Depth First Search，DFS） 與 廣度優先搜尋（Breadth First Search，BFS） 來做處理。

方法1: DFS

描述

dfs相信大家都很熟悉了把XD

深度優先搜尋（Depth First Search，DFS） 簡單來說就是透過一連串的遞迴（recursion）來對樹（tree）、圖（graph）等資料結構進行搜尋。這種演算法會盡可能的往樹或圖的深處走，因此稱為深度優先搜尋。

IMG_0183
上圖範例的走訪順序為: A->B->C->D->E->F

上方的走訪方式是二元樹走訪中的先序遍歷(Preorder Traversal) ，之後有時間會再寫一篇文來介紹二元樹走訪。

以本題為例，我們會遍歷一次所有格子。在遍歷的途中，我們會對每個符合子島嶼條件的點做DFS，遍歷完後便可得到子島嶼總數。

每次DFS中，我們會針對每個點做以下三件事：

  1. 對該點做邊界檢測：若超出地圖邊界，回傳0
  2. 偵測該點是否為海：若為海，回傳0
  3. 偵測該點是否為違反子島嶼規則的陸地：若違反規則，則回傳-1
  4. 對上、下、左、右四個相鄰點做DFS
  5. 將該點的值改為0，避免重複走訪

必須要整座島嶼的陸地皆符合子島嶼規則，該島嶼才能稱作是子島嶼

Code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// Author: Toast1001
// Method: dfs
// TC: O(n*m)
// SC: O(n*m)

static const auto Init = []{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int32_t ans = 0; // sub-islands 總數
        
        // 遍歷 grid2 上所有點
        for(int32_t i = 0;i < grid2.size();i++){
            for(int32_t j = 0;j < grid2[0].size();j++){
                // 若該點符合 sub-island 規則，則進行 dfs
                if(grid1[i][j] == 1 && grid2[i][j] == 1){
                    int32_t temp = dfs(i, j, grid1, grid2);
                    if(temp == 1)ans++; // 若該點所連結的所有陸地可組合成一座 sub-island，則總數加一
                }
            }
        }
        return ans; // 回傳 sub-island 總數
    }
    
private:
    // 方位陣列（dfs 用）
    int32_t dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    // dfs
    int32_t dfs(int32_t i, int32_t j, vector<vector<int32_t>>& grid1, vector<vector<int32_t>>& grid2){
        int32_t ans = 1; // 回傳值預設1
        if(i < 0 || i >= grid2.size() || j < 0 || j >= grid2[0].size())return 0; // 邊界檢測
        if(grid2[i][j] == 0)return 0; // 檢測是否為海洋
        
        // 檢測是否為違反 sub-island 規則的陸地
        if(grid1[i][j] == 0){
            ans = -1;
        }
        
        grid2[i][j] = 0; // 更新該點為海洋
        
        // 對周圍四點做 dfs
        for(int32_t k = 0;k < 4;k++){
            
            // 若周圍有陸地違反 sub-island 規則
            // 則與該點相連的陸塊皆不符合違反 sub-island 規則
            // 必須用 -1 紀錄
            ans = min(ans, dfs(i + dir[k][0], j + dir[k][1], grid1, grid2));
        }
        
        if(ans == -1)return ans; // 若該島嶼違反 sub-island 規則，回傳 -1
        return 1;
    }
};

時間複雜度（Time Complexity）：O(n*m)

空間複雜度（Time Complexity）：O(n*m)

結果

由於在做 DFS 的時候都有把走訪過的點紀錄，使所有點最多只會走訪一次，本質上就是在遍歷二維陣列，因此效率較高。

image

方法2: BFS

描述

bfs相信大家也很熟悉了把XD

廣度優先搜尋（Breadth First Search，BFS） 與 DFS 一樣，可用於樹與圖的遍歷。不一樣的是，BFS 會將同一深度的點都走訪完成後，再往下一層前進。這種演算法傾向系統地展開並檢查圖中的所有節點，故稱為廣度優先搜尋。

IMG_0184
上圖範例的走訪順序為: A->B->E->C->D->F

遍歷時的邏輯大致與 DFS 一樣，在遍歷的途中，我們會對每個符合子島嶼條件的點做DFS，遍歷完後便可得到子島嶼總數。

Code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// Author: Toast1001
// Method: dfs
// TC: O(n*m)
// SC: O(n*m)

static const auto Init = []{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        // 初始化數字
        int32_t ans = 0; // 子島嶼總數
        int32_t m = grid2.size();
        int32_t n = grid2[0].size();
        bool makeup; // 判斷陸地是否為子島嶼
        int32_t x, y, nx, ny;
        queue<int32_t> qx, qy; // 儲存點的queue
        
        // 遍歷
        for(int32_t i = 0;i < m;i++){
            for(int32_t j = 0;j < n;j++){
                
                // 若該點在grid2為陸地，則走訪
                if(grid2[i][j]){
                    grid2[i][j] = 0; // 更新該點為海洋
                    makeup = (grid1[i][j] == 1); // 判斷陸地是否為子島嶼
                    qx.push(i);
                    qy.push(j);
                    
                    // 利用queue做bfs
                    while(!qx.empty()){
                        x = qx.front();
                        y = qy.front();
                        qx.pop();
                        qy.pop();
                        
                        // 尋找下一個存入queue的點
                        for(int32_t k = 0;k < 4;k++){
                            nx = x + dx[k];
                            ny = y + dy[k];
                            
                            // 邊界檢測與海陸檢測
                            if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid2[nx][ny]){
                                qx.push(nx);
                                qy.push(ny);
                                grid2[nx][ny] = 0; // 更新為海洋
                                makeup &= (grid1[nx][ny] == 1); // 判斷陸地是否為子島嶼
                            }
                        }
                    }
                    // 若該島嶼為子島嶼，則總數+1
                    if(makeup){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
private:
    int32_t dx[4] = {0, 1, 0, -1};
    int32_t dy[4] = {1, 0, -1, 0};
};

時間複雜度（Time Complexity）：O(n*m)

空間複雜度（Time Complexity）：O(n*m)

結果

本題使用 DFS 與 BFS 效率差不多，跑出來的成果都不錯。

image

小結

這種 DFS 與 BFS 問題常常在面試白板題與競賽中出現，如果學會的話，會對未來很有幫助哦～

那就老樣子啦，吐司寫 LeetCode，我們下次見，bye~ bye~

類題

LeetCode:
200. Number of Islands
1992. Find All Groups of Farmland

推薦閱讀
吐司的 2024 回顧 吐司的 2024 回顧
推薦閱讀
吐司的 2024 回顧 吐司的 2024 回顧
留言
此頁目錄
吐司寫LeetCode :1905. Count Sub Islands
  1. 題目原文
  2. 題解
  3. 想一想
  4. 方法1: DFS
    1. 描述
    2. Code:
    3. 時間複雜度（Time Complexity）：O(n*m)
    4. 空間複雜度（Time Complexity）：O(n*m)
    5. 結果
  5. 方法2: BFS
    1. 描述
    2. Code:
    3. 時間複雜度（Time Complexity）：O(n*m)
    4. 空間複雜度（Time Complexity）：O(n*m)
    5. 結果
  6. 小結
  7. 類題