C++實現LeetCode之島嶼數量的示例分析

這篇文章主要為大家展示了“C++實現LeetCode之島嶼數量的示例分析”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“C++實現LeetCode之島嶼數量的示例分析”這篇文章吧。

[LeetCode] 200. Number of Islands 島嶼的數量

Given a 2d grid map of '1's (land) and '0's (water), count 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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

這道求島嶼數量的題的本質是求矩陣中連續區域的個數，很容易想到需要用深度優先搜索 DFS 來解，我們需要建立一個 visited 數組用來記錄某個位置是否被訪問過，對于一個為 ‘1' 且未被訪問過的位置，遞歸進入其上下左右位置上為 ‘1' 的數，將其 visited 對應值賦為 true，繼續進入其所有相連的鄰位置，這樣可以將這個連通區域所有的數找出來，并將其對應的 visited 中的值賦 true，找完相鄰區域后，將結果 res 自增1，然后再繼續找下一個為 ‘1' 且未被訪問過的位置，以此類推直至遍歷完整個原數組即可得到最終結果，代碼如下：

解法一：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                helper(grid, visited, i, j);
                ++res;
            }
        }
        return res;
    }
    void helper(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
        visited[x][y] = true;
        helper(grid, visited, x - 1, y);
        helper(grid, visited, x + 1, y);
        helper(grid, visited, x, y - 1);
        helper(grid, visited, x, y + 1);
    }
};

當然，這種類似迷宮遍歷的題目 DFS 和 BFS 兩對好基友肯定是形影不離的，那么 BFS 搞起。其實也很簡單，就是在遍歷到 ‘1' 的時候，且該位置沒有被訪問過，那么就調用一個 BFS 即可，借助隊列 queue 來實現，現將當前位置加入隊列，然后進行 while 循環，將隊首元素提取出來，并遍歷其周圍四個位置，若沒有越界的話，就將 visited 中該鄰居位置標記為 true，并將其加入隊列中等待下次遍歷即可，參見代碼如下：

解法二：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        vector<int> dirX{-1, 0, 1, 0}, dirY{0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                ++res;
                queue<int> q{{i * n + j}};
                while (!q.empty()) {
                    int t = q.front(); q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int x = t / n + dirX[k], y = t % n + dirY[k];
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0' || visited[x][y]) continue;
                        visited[x][y] = true;
                        q.push(x * n + y);
                    }
                }
            }
        }
        return res;
    }
};

以上是“C++實現LeetCode之島嶼數量的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！