题意

给定一个矩阵，计算其中只由1构成的连通块的数量。

思路

对于这类题目，我们可以使用FloodFill算法，从某个点开始向四周扩展，直到无法再扩展为止。以此为基础构建深度优先搜寻，将每个为1的点向外将上下左右的1变为0，然后往4个方向继续遍历，最后计算所得的连通块数量就是岛屿数量。

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int n,m,ans,dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};//方向数组
    bool Grid[205][205];
    void dfs(int x,int y)
    {
	    if (x>n||y>m||x<0||y<0)return;
	    Grid[x][y]=false;//标记为没有
	    for (int i=0;i<4;i++)if (Grid[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);//如果有才搜
    }//搜索
    int solve(vector<vector<char> >& grid) {
        // write code here
        n=grid.size();
        m=grid[0].size();
        memset(Grid,false,sizeof Grid);
        for(int i=0;i<n;i++)
	    for(int j=0;j<m;j++)
        {
            if(grid[i][j]=='0') Grid[i][j]=false;
            else Grid[i][j]=true;//把地图转化为bool数组
        }
        for(int i=0;i<n;i++)
	    for(int j=0;j<m;j++)
            if (Grid[i][j]) {ans++;dfs(i,j);}//搜索连通块数量
        return ans;
    }
};

复杂度分析

时间复杂度：$O(nm)O(nm)$，最坏情况要扫遍整个地图。

空间复杂度：$O(nm)O(nm)$，存储地图所用空间。