[leetcode] Number of Islands II

Number of Islands II

A 2d grid map of `m` rows and `n` columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. 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:

Given `m = 3, n = 3`, `positions = [[0,0], [0,1], [1,2], [2,1]]`.
Initially, the 2d grid `grid` is filled with water. (Assume 0 represents water and 1 represents land).

```0 0 0
0 0 0
0 0 0
```

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

```1 0 0
0 0 0   Number of islands = 1
0 0 0
```

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

```1 1 0
0 0 0   Number of islands = 1
0 0 0
```

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

```1 1 0
0 0 1   Number of islands = 2
0 0 0
```

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

```1 1 0
0 0 1   Number of islands = 3
0 1 0
```

We return the result as an array: `[1, 1, 2, 3]`

Update: (2015/11/13)
If you are using Java, the parameter `List<int[]> positions` had been changed to `int[][] positions`. Please click on the reload button above the code editor to reset the code definition.

Use unionset algorithm.

Take care of the index checking, since I compress the 2d matrix to 1d array.

```class Solution {
public:
vector<int> ans; // overflow?
vector<int> unionset; // overflow?
unordered_set<int> roots;

vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
ans.clear();
roots.clear();
unionset = vector<int>(m*n, -1);// connect all water cells to root -1
int dict[] = {-1, 1, -n, n};
for(auto it = positions.begin(); it != positions.end(); it++){
int idx = it->first * n + it->second;
if(unionset[idx] != -1){
// not a water cell
// num of island do not change
ans.push_back(roots.size());
}
else{
// find neighbours, try to merge
set(idx, idx);
roots.insert(idx);
for(int i = 0; i < 4; i++){
int nidx = idx + dict[i];
// not a valid neighbour
if(nidx < 0 || nidx >= m * n || ((nidx / n != idx / n) && (nidx % n != idx % n))){ // previously a BUG HERE
continue;
}
// neighbour is a water cell
if(unionset[nidx] == -1){
continue;
}
int root = find(nidx);
if(root != idx){
set(root, idx);
roots.erase(root);
}

}
}
ans.push_back(roots.size());
}
return ans;
}
int find(int idx){
//base condition
if(unionset[idx] == idx){
return idx;
}
else{
int root = find(unionset[idx]);
unionset[idx] = root;
return root;
}
}
void set(int idx, int root){
unionset[idx] = root;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.