解决岛屿问题

简介: 解决岛屿问题

Island

问题

整形二维数组arr中分布着许多1,其余都是0,彼此相连的一群1构成一个岛屿,斜线不表示相连,求岛屿的数量

思路

遍历数组,遇到1进行感染infect,将1改成2

实现

void infect(vector<vector<int>>& arr,int i,int j)
{
    /******注意边界******/
    if(i > arr.size() || i < 0 || j > arr[0].size() || j < 0 || arr[i][j] != 1) return;
    arr[i][j] = 2;
    infect(arr,i - 1,j);
    infect(arr,i + 1,j);
    infect(arr,i,j + 1);
    infect(arr,i,j - 1);
}
int Island(vector<vector<int>> arr)
{
    int res = 0;
    for(int i = 0;i < arr.size();i++)
    {
        for(int j = 0;j < arr[0].size();j++)
        {
            if(arr[i][j] == 1)
            {
                res++;
                infect(arr,i,j);
            }
        }
    }
    return res;
}

总结

如果二维数组过大,那这个方法就不好使了,所以可以将数组分为两部分,再利用并查集的思想解决

目录
相关文章
|
6月前
leetcode-695:岛屿的最大面积
leetcode-695:岛屿的最大面积
54 0
|
6月前
leetcode-463:岛屿的周长
leetcode-463:岛屿的周长
34 0
|
6月前
凸多边形的划分(区间dp)
凸多边形的划分(区间dp)
46 0
|
6月前
|
存储 算法 程序员
【算法训练-搜索算法 一】【DFS网格搜索框架】岛屿数量、岛屿的最大面积、岛屿的周长
【算法训练-搜索算法 一】【DFS网格搜索框架】岛屿数量、岛屿的最大面积、岛屿的周长
125 0
Leecode 695. 岛屿的最大面积
Leecode 695. 岛屿的最大面积
37 0
leetcode 695 岛屿的最大面积
leetcode 695 岛屿的最大面积
67 0
leetcode 695 岛屿的最大面积
leetcode 463 岛屿的周长
leetcode 463 岛屿的周长
69 0
leetcode 463 岛屿的周长
洛谷P3194 [HNOI2008]水平可见直线(计算几何+单调栈)
洛谷P3194 [HNOI2008]水平可见直线(计算几何+单调栈)
108 0
洛谷P3194 [HNOI2008]水平可见直线(计算几何+单调栈)
|
定位技术
宝岛探险(求岛屿大小,染色法) 宽搜 深搜
宝岛探险(求岛屿大小,染色法) 宽搜 深搜
宝岛探险(求岛屿大小,染色法) 宽搜 深搜
|
定位技术
用并查集解决「岛屿最大面积问题」
用并查集解决这个问题时间花费会比 DFS 和 BFS 更大,但是最主要的还是学习并查集的思想以及如何实现。
91 0