给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
[[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]]
3
01矩阵范围<=200*200
1. 岛屿的定义：一个 1 周围上下左右全是 0，即为一个岛屿。（注意：grid 数组内的 1、0 均为char型字符，非整型）
2. 示例1 中的三个岛屿：左上角三个1、中间四个1、右下角三个一，分别组成三个岛屿。
3. 每块岛屿可以看成相连的一个个节点。
4. 遍历整块大陆。
5. 找到根节点（第一个陆地 1），岛屿数量加一。
6. 将根节点标记为已探索 更改为0。
7. 探索整块岛屿的范围就是根节点的上下左右节点，将探索过的1 标记为 0 。
8. 遍历殆尽时证明一块岛屿已找到。
9. 继续寻找下一个岛屿 根节点（为1的陆地）。
Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。
因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。
在 GNU Go 和 扫雷 中，Flood Fill算法被用来计算需要被清除的区域。
由上述定义可看出该题是典型的Flood fill算法类型例题，将岛屿与水分开，并染成特定颜色，以记录已累加过该岛屿。
DFS（深度优先搜索）：从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是水），依次访问其他相邻1节点到顶点
BFS（广度优先搜索）：从一个为1的根节点开始访问，每次向下访问一个节点，直到访问到最后一个顶点
并查集：也被称为联合查找数据结构，因为它主要由联合、查找两个过程实现：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
针对该题即 先以一个根节点1作为初始节点，判断周围节点是否为1，如果是则新建一个集合并把该节点作为父节点。之后遍历下一个节点，如果是1则查找该节点的父节点（即第一个节点），并把该节点周围为1的节点的父节点全部指向该节点的父节点，以此类推，直到把该块岛屿所有1 节点加入同一个集合。最后集合个数（父节点的个数）即为岛屿数量
时间复杂度 : O(M×N)，其中 M 和 N 分别为行数和列数。
空间复杂度 : 最坏情况下为 O(M×N)，此时整个网格均为陆地，深度优先搜索的深度达到 M×N。
Java：
1 import java.util.*; 2 3 4 public class Solution { 5 /** 6 * 判断岛屿数量 7 * @param grid char字符型二维数组 8 * @return int整型 9 */ 10 public int solve (char[][] grid) { 11 // write code here 12 if(grid == null || grid.length == 0){ 13 return 0; 14 } 15 // 外层数组长度 16 int nr = grid.length; 17 // 内层数组长度 18 int nc = grid[0].length; 19 // 岛屿个数 20 int num_isLands = 0; 21 // 循环矩阵 22 for(int r = 0; r < nr; r++){ 23 24 for(int c = 0; c < nc; c++){ 25 // 找到第一块陆地： 岛屿节点 26 if(grid[r][c] == ‘1‘){ 27 // 岛屿数量+1 28 num_isLands ++; 29 // 查看岛屿的范围 30 dfs(grid,r,c); 31 } 32 } 33 } 34 return num_isLands; 35 } 36 37 // 查看岛屿范围并标记 38 public void dfs(char[][] grid,int r,int c){ 39 // 外层数组长度 40 int nr = grid.length; 41 // 内层数组长度 42 int nc = grid[0].length; 43 // 条件判断 如果该节点的尽头为海洋0 就返回继续探索 44 if(r<0 || c<0 || r >= nr || c >= nc || grid[r][c] == ‘0‘){ 45 return; 46 } 47 // 将探索的节点标记为 0 48 grid[r][c] = ‘0‘; 49 // 查看子节点的上下左右 50 dfs(grid,r+1,c); 51 dfs(grid,r-1,c); 52 dfs(grid,r,c-1); 53 dfs(grid,r,c+1); 54 } 55 56 57 }
原文：https://www.cnblogs.com/sonyau/p/14521675.html