leetcode-200. 岛屿数量

flood fill 算法

给定二位矩阵，搜索其中的1的连通块的数量

注意：

• 岛屿问题：LC695/LC827/LC463/LC200，+L1254+ LC994
• 被问到深度优先和广度优先的差别、计算时间空间复杂度
• 深度OR广度OR并查集都可
• 微软follow up题：827. 最大人工岛，MS follow up: 只允许一个水变成陆地，最大岛屿面积是多少？****827. 最大人工岛****
• leetcode 694 不同的岛屿数量
• DFS+BFS+并查集
• 网易互娱笔试
• 美团二面
• 火山一面
• 字节AI LAB一面
• 抖音后端二面
• 飞书2 15

方法1：DFS, 找是1的陆地

typedef pair<int,int> PII;

class Solution {
public:
    // 全局变量
    vector<vector<char>> g;
    // 先定义4个方向
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    int cnt = 0;// 记录连通块的个数
    
    int numIslands(vector<vector<char>>& grid) {
        g = grid;

        for (int i = 0; i < g.size(); i ++)
        {
            for (int j = 0; j < g[i].size(); j ++)
            {
                // 找1的连通块
                if (g[i][j] == '1')
                {
                    dfs(i,j);
                    // bfs({i, j});
                    cnt ++; // 上面每搜完一个连通块，就把cnt+1
                }
            }
        }
        return cnt;
    }

    // dfs代码
    void dfs(int x, int y)
    {
        // 遍历过的位置，变为0, 防止重复遍历
        g[x][y] = '0';
        // 向4个方向找1
        for (int i = 0; i < 4; i ++)
        {
            // 计算 下一个位置的坐标(a,b)
            int a = x + dx[i], b = y + dy[i];
            // 下一个位置(a,b)上也是1，就继续dfs
            if (a >= 0 && a < g.size() && b >= 0 && b < g[0].size() && g[a][b] == '1')
                dfs(a, b);
        }
    }
};

方法：DFS ， 避免0和2

typedef pair<int,int> PII;

class Solution {
public:
    // 全局变量
    vector<vector<char>> g;
    // 先定义4个方向
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    int cnt = 0;// 记录连通块的个数
    
    int numIslands(vector<vector<char>>& grid) {
        g = grid;

        for (int i = 0; i < g.size(); i ++)
        {
            for (int j = 0; j < g[i].size(); j ++)
            {
                // 找1的连通块
                if (g[i][j] == '1')
                {
                    dfs(i,j);
                    // bfs({i, j});
                    cnt ++; // 上面每搜完一个连通块，就把cnt+1
                }
            }
        }
        return cnt;
    }


    // dfs代码
    void dfs(int x, int y)
    {
        // 遍历过的位置，标记为2, 防止重复遍历
        g[x][y] = '2';
        
        // 向4个方向找1
        for (int i = 0; i < 4; i ++)
        {
            // 计算 下一个位置的坐标(a,b)
            int a = x + dx[i], b = y + dy[i];

            // 判断 base case
            if (a < 0 || a >= g.size() || b < 0 || b >= g[0].size()) continue;
            if (g[a][b] == '2' || g[a][b] == '0') continue;
            dfs(a,b);

            // 下一个位置(a,b)上也是1，就继续dfs
            // if (a >= 0 && a < g.size() && b >= 0 && b < g[0].size() && g[a][b] == '1')
            //     dfs(a, b);
        }
    }
};

方法2：BFS

typedef pair<int,int> PII;

class Solution {
public:
    // 全局变量
    vector<vector<char>> g;
    // 先定义4个方向
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    int cnt = 0;// 记录连通块的个数
    
    int numIslands(vector<vector<char>>& grid) {
        g = grid;

        for (int i = 0; i < g.size(); i ++)
        {
            for (int j = 0; j < g[i].size(); j ++)
            {
                // 找1的连通块
                if (g[i][j] == '1')
                {
                    // dfs(i,j);
                    bfs({i, j});
                    cnt ++; // 上面每搜完一个连通块，就把cnt+1
                }
            }
        }
        return cnt;
    }

    void bfs(PII p)
    {
        queue<PII> q;
        q.push(p);

        while (!q.empty())
        {
            PII t = q.front();
            q.pop();

            // 拓展4个方向
            for (int i = 0; i < 4; i ++)
            {
                // 下一个位置的坐标(a,b)
                int a = t.first + dx[i], b = t.second + dy[i];
                if (a < 0 || a >= g.size() || b < 0 || b >= g[0].size() || g[a][b] == '0')
                    continue;
                g[a][b] = '0';
                q.push({a,b});
            }
        }
    }
};