题解 | #岛屿数量#

岛屿数量

http://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e

描述

这是一篇面对初级coder的题解。
知识点：搜索（BFS、DFS）二维vector使用
难度：二星

题解

给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右）判断岛屿个数。

分析：

由于寻找的岛屿形不规整，动态规划时容易造成岛屿的分离所以采用搜索算法

对每一个等于“1”的点（岛屿）向其四个方向搜索为节约空间采用不保留原数组的形式，直接在原数组上置零：

方法一：深度优先搜索(DFS)

对于每一个等于‘1’的点：岛屿递归进行深度优先搜索，

class Solution {
public:
    int a[4]={1,0,-1,0};//便于遍历四个方向
    int b[4]={0,1,0,-1};
    int dfs(vector<vector<char> >& grid,int i,int j,int l,int w){
        grid[i][j]='0';//原数组上清零
        for(int k=0;k<4;k++){//四个方向
            if(i+a[k]>=0&&i+a[k]<l&&j+b[k]>=0&&j+b[k]<w&&grid[i+a[k]][j+b[k]]=='1'){//相邻1
                dfs(grid,i+a[k],j+b[k],l,w);//dfs 递归 用函数自带的栈
            }
       }
        return 0;
    }
    int solve(vector<vector<char> >& grid) {
        int ans=0;//返回答案
        int l=grid.size() ,w=grid[0].size();//矩阵长宽
        for (int i=0;i<l;i++){//双重循环
            for (int j=0;j<=w;j++) {
                if(grid[i][j]=='1'){//上岛屿
                    dfs(grid,i,j,l,w);//dfs 
                    ans++;//岛屿数量+1
                }
            }
        }
        return ans;
        // write code here
    }
};

时间复杂度 $O(mn)$ ：其中 $m$ 和 $n$ 分别为行数和列数，双重遍历时间

空间复杂的 $O(mn)$ ：在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 $mn$

运行时间： 8 ms 占用内存：676K

方法二：广度优先搜索(BFS)

对于每一个等于‘1’的点：岛屿递归进行广度优先搜索，

采用一个队列存元素不断将搜索到的元素加入队列同时将队列中元素对应点置空出队列。

class Solution {
public:
    struct point{ //定义点结构体方便维护队列
        int x;
        int y;
    };
    int a[4]={1,0,-1,0};//便于遍历四个方向
    int b[4]={0,1,0,-1};
    int bfs(vector<vector<char> >& grid,int i,int j,int l,int w){
        int ans=1;
        queue<point> q;//定义队列存点
        point tmp1,tmp2;//队列一次存x，y坐标
        tmp1.x=i;
        tmp1.y=j;
        grid[tmp1.x][tmp1.y]='0';//原数组清零
        q.push(tmp1);
        while(q.size()!=0){//直至队列为空
            tmp1=q.front();//取队列头
            q.pop();//出队列
            for(int i=0;i<4;i++){//四个方向
                if(tmp1.x+a[i]>=0&&tmp1.x+a[i]<l&&tmp1.y+b[i]>=0&&tmp1.y+b[i]<w&&grid[tmp1.x+a[i]][tmp1.y+b[i]]=='1'){ //相邻1的四个点 不是边界外且等于1（是岛屿）
                    tmp2.x=tmp1.x+a[i];//存队列x
                    tmp2.y=tmp1.y+b[i];//存队列y
                     grid[tmp2.x][tmp2.y]='0';//原数组清零
                    q.push(tmp2);//入队列
                    ans++;//计数++
                }
            }
        }
        return 1;
    }
    int solve(vector<vector<char> >& grid) {
        int ans=0;//返回答案
        int l=grid.size() ,w=grid[0].size();//矩阵长宽
        for (int i=0;i<l;i++){
            for (int j=0;j<=w;j++) {
                if(grid[i][j]=='1')//是岛屿
                    ans+=bfs(grid,i,j,l,w);//bfs
            }
        }
        return ans;
        // write code here
    }
};

时间复杂度 $O(mn)$ ：其中 $m$ 和 $n$ 分别为行数和列数，双重遍历时间