C++實現(xiàn)LeetCode(200.島嶼的數(shù)量)

更新時間：2021年07月27日 15:36:03 作者：Grandyang

這篇文章主要介紹了C++實現(xiàn)LeetCode(200.島嶼的數(shù)量),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下

[LeetCode] 200. Number of Islands 島嶼的數(shù)量

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

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

解法一：

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 來實現(xiàn)，現(xiàn)將當前位置加入隊列，然后進行 while 循環(huán)，將隊首元素提取出來，并遍歷其周圍四個位置，若沒有越界的話，就將 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;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/200

類似題目：

Number of Islands II

Surrounded Regions

Walls and Gates

Number of Connected Components in an Undirected Graph

Number of Distinct Islands

Max Area of Island

參考資料：

https://leetcode.com/problems/number-of-islands/

https://leetcode.com/problems/number-of-islands/discuss/56589/C%2B%2B-BFSDFS