LeetCode/岛屿数量(连通域数量)
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
1. 遍历递归
遍历每一个位置，如果存在，则递归其周围区域，并使总区域数加一，
递归同时要四个方向都进行递归，并把递归的区域标识避免重复递归陷入死循环
遍历递归
class Solution {
public:
int numIslands(vector>& grid) {
int sum = 0;
int m = grid.size();
int n = grid[0].size();
for(int i=0;i>& grid,int i,int j){
grid[i][j]=0+'0';
if(i0&&grid[i-1][j]=='1') search(grid,i-1,j);//往上
if(j>0&&grid[i][j-1]=='1') search(grid,i,j-1);//往左
}
};
2. 并查集
并查集的方法首先要为每一个点建立集合，接着写出判断两个点是否属于一个集合的方式
最后不断合并集合，在该题中，最终集合的数量就是岛屿的数量，每合并一次岛屿数量减一
这里不考虑使用类模板的方式，因为建立集合set，set的合并，判断相邻元素属于哪个set，这些操作都会花费大量的时间和空间
直接用一个一维数组存储，每个位置的值为他们位置大小，这样就把不同集合区分开来
后面合并更新时，当他们值一样即说明是同一集合，合并时将其中一个集合元素值全部转换为另一集合元素值，即表示合并
这里我们用静态指针(索引)的方式，来方便集合的合并和元素加入
一维数组并查集
class Solution {
public:
vector parent;
int sum;
int numIslands(vector>& grid) {
int m = grid.size();
int n = grid[0].size();
int index;
//初始化parent数组，记录初始岛屿数量
for (int i = 0; i < m; i++)
for(int j = 0; j < n; j++){
index = i * n + j;
parent.push_back(index);//后面根据索引建立集合簇
if(grid[i][j] == '1')
sum++; //记录初始岛屿数量
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++){
index = i * n + j; //从左往右，从上往下遍历合并全部岛屿
if (grid[i][j] == '1') {
if (i+1 < m && grid[i+1][j] == '1') { //下
unions(index, (i + 1) * n + j);
}
if (j+1