Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
代码语言：javascript复制11110110101100000000Answer: 1
Example 2:
代码语言：javascript复制11000110000010000011Answer: 3
相邻方向的1视为一块，这题其实本质就是求子块的数量。
并查集，如果一个点为“1”，那这个点和它左方上方为“1”的点属于一个联通块，并到一个集合就可以了。
如果一个点为“0”，那么把它的父节点置为-1。
最后统计出现的不为“-1”的不同数字的个数就可以了。
代码语言：javascript复制class Solution {
public:
vector<int> set;
int find(int x)
{
if(x!=set[x]) set[x] = find(set[x]);
return set[x];
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if(m == 0) return 0;
int n = grid[0].size();
for(int i = 0;i < m * n; i ) set.push_back(i);
for(int i = 0; i < m ; i )
{
for(int j = 0; j < n; j )
{
int x = i * n j;
if(grid[i][j] == '0')
{
set[x] = -1;
continue;
}
if(i != 0 && grid[i-1][j] == '1')
{
int y = (i - 1) * n j;
set[find(x)] = find(y);
}
if(j != 0 && grid[i][j-1] == '1')
{
int y = i * n j -1;
set[find(x)] = find(y);
}
}
}
int res = 0;
unordered_map<int, int> mp;
for(int i = 0 ;i < m * n ; i )
{
if(set[i] == -1) continue;
int y = find(i);
if(!mp[y])
{
res ;
mp[y] = 1;
}
}
return res;
}
};
