快捷導(dǎo)航

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

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

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

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

解法一：

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);
    }
};

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

解法二：

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

https://leetcode.com/problems/number-of-islands/discuss/56359/Very-concise-Java-AC-solution

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(200.島嶼的數(shù)量)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)島嶼的數(shù)量內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: