给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
因为岛屿是连通着的1，很容易想到DFS和BFS，从一个1点出发，可以把它连通着的所有1（连通的邻接点有四个方向：上下左右）搜索出来，这就是一个岛屿。而我们进行几次dfs/bfs搜索就是一共有几个岛屿。详细DFS和BFS的搜索方法介绍见图/树的遍历：深度优先遍历DFS和广度优先遍历BFS详解与java实现。
具体代码怎么设计实现，就有以下几个问题：① 从哪个1出发，怎么选择每个岛屿的第一个1？② 怎么确保下一个搜索选择的1是没有被搜索过的岛屿？
上述问题的解决方法：本来想着是将二维数组中所有的1用另一种数据结构存储起来，依次遍历作为搜索开始点，搜索过的1就从存储结构里删除；等这次搜索结束后，从存储结构里的下一个1开始下一次搜索。但是实现起来比较麻烦，也需要额外的内存空间。
另一种更好的解决方法就是在grid数组里原地搜索，不占用额外的内存空间。
递归求解
需要注意的是，dfs的递归求解中，遍历到每一个点时，在递归它的邻接点之前，一定要确保它的那个邻接点存在，因为不存在就不用判断/搜索这个点。而这种判断情况很复杂，因为邻接点存在的条件很多样。所以我们写代码时可以采用排除法，反向思考，不判断点是否存在，而是判断点是否不存在，将不存在的情况排除。
具体操作：递归每个点时，不判断每个邻接点是否存在再递归这个邻接点，而是假设都存在先递归邻接点，然后在每次递归的方法里先判断这个点存不存在，将不存在的情况(比如在方格外或不满足条件)列出来，直接返回不用继续递归。
在该题中，邻接点存在的条件是：
时间复杂度：O(mn),m和n分别为行数和列数
空间复杂度：O(mn),因为dfs的深度最坏为整个陆地为mn
class Solution {
public int numIslands(char[][] grid) {
//深度优先搜索 递归
int res = 0;
int m = grid.length;//行数
//特殊情况
if(grid == null ||m == 0) return 0;
//因为当rown等于0时，coln根本算不出来，所以要先判断
int n = grid[0].length; //列数
for(int i = 0;i < m;i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
res++;
//从(i,j)位置开始搜索，将搜索到的1值都标记为0，说明已经访问过，属于这次搜索的岛屿中的，下一次深度搜索已经不需要了。
dfs(i,j,grid);
}
}
}
return res;
}
public void dfs(int i, int j,char[][] grid){
int m = grid.length;//行数
int n = grid[0].length; //列数
//如果当前值已在边界外 或者当前值为0就直接返回，因为只需要搜索边界内的1值
if(i >= m || j>=n || i < 0 || j < 0 || grid[i][j] == '0') return;
//当当前访问到的(i,j)值标记为0，表示已访问过
grid[i][j] = '0';
//递归搜索它的四个邻接点
dfs(i+1,j,grid);//下邻接点
dfs(i-1,j,grid);//上邻接点
dfs(i,j+1,grid);//右邻接点
dfs(i,j-1,grid);//左邻接点
}
}
主循环和dfs解法一样，不同的就在于搜索连通的1的方式不同。BFS主要通过队列来实现，将初始1压入队列，然后弹出一个1将其符合条件的邻接点压入队列中，再弹出1，再压入它的邻接点们~；直至队列为空表示此次BFS结束。
时间复杂度：O(mn),m和n分别为行数和列数
空间复杂度：O(min(m,n)),因为bfs最坏的情况下队列的长度可达到min(m,n)
class Solution {
public int numIslands(char[][] grid) {
//bfs 队列
int res = 0;
int m = grid.length;//行数
//特殊情况
if(grid == null ||m == 0) return 0;
//因为当rown等于0时，coln根本算不出来，所以要先判断
int n = grid[0].length; //列数
//初始化一个队列
Queue<int[]> queue = new LinkedList<>();
for(int i = 0;i < m;i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '1'){
res++;
//从(i,j)位置开始搜索，将搜索到的1值都标记为0，说明已经访问过，属于这次搜索的岛屿中的，下一次深度搜索已经不需要了。
grid[i][j] = '0';
//bfs：将该点的所有值为1的邻接点加入队列中，队列每弹出一个点，继续加入该点的所有邻接点直到队列空为止
queue.offer(new int[]{i,j});//将初始1压入队列
while(!queue.isEmpty()){
int[] temp = queue.poll();//弹出一个元素temp
//将temp的邻接点压入队列中
//temp的上邻接点存在的话
if(temp[0]-1 >=0 && grid[temp[0]-1][temp[1]] == '1'){
queue.offer(new int[]{temp[0]-1,temp[1]});
grid[temp[0]-1][temp[1]] = '0';
}
//temp的下邻接点存在的话
if(temp[0]+1 <m && grid[temp[0]+1][temp[1]] == '1'){
queue.offer(new int[]{temp[0]+1,temp[1]});
grid[temp[0]+1][temp[1]] = '0';
}
//temp的左邻接点存在的话
if(temp[1]-1 >=0 && grid[temp[0]][temp[1]-1] == '1'){
queue.offer(new int[]{temp[0],temp[1]-1});
grid[temp[0]][temp[1]-1] = '0';
}
//temp的右邻接点存在的话
if(temp[1]+1 <n && grid[temp[0]][temp[1]+1] == '1'){
queue.offer(new int[]{temp[0],temp[1]+1});
grid[temp[0]][temp[1]+1] = '0';
}
}
}
}
}
return res;
}
}
参考：leetcode官方题解