描述

这是一篇面对初级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
    }
};

时间复杂度：其中 和 分别为行数和列数，双重遍历时间

空间复杂的：在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到
 运行时间： 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
    }
};

时间复杂度：其中 和 分别为行数和列数，双重遍历时间

空间复杂的：在最坏情况下，整个网格均为陆地，广度优先搜索的队列长度达到 
运行时间： 7 ms 占用内存：716K

总结

对于这两个搜索方法，其实我们是可以轻松的看出来，他们有许多差异与许多相同点的。

1.数据结构上的运用

DFS用递归的形式，用到了栈结构，先进后出。

BFS选取状态用队列的形式，先进先出。

2.复杂度

DFS的复杂度与BFS的复杂度大体一致，不同之处在于遍历的方式与对于问题的解决出发点不同，DFS适合目标明确，而BFS适合大范围的寻找。

3.思想

思想上来说这两种方法都是穷竭列举所有的情况。