Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.
Notice
0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Have you met this question in a real interview?
Yes
Example
Givenn=3,m=3, array of pair A =[(0,0),(0,1),(2,2),(2,1)].
return[1,1,2,2].
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
/**
* @param n an integer
* @param m an integer
* @param operators an array of point
* @return an integer array
*/
vector<int> numIslands2(int n, int m, vector<Point>& operators) {
// Write your code here
vector<int> res;
if (n == 0 || m == 0 || operators.empty()) {
return res;
}
father.resize(n * m);
for (int i = 0; i < father.size(); ++i) {
father[i] = i;
}
int cnt = 0;
vector<vector<bool>> isIsland(n, vector<bool>(m, false));
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto& point : operators) {
if (isIsland[point.x][point.y]) {
continue;
}
isIsland[point.x][point.y] = true;
++cnt;
int ptId = convertToId(point.x, point.y, m);
for (auto& dir : dirs) {
int nx = point.x + dir[0];
int ny = point.y + dir[1];
if (IsInside(nx, ny, n, m) && isIsland[nx][ny]) {
int newPtId = convertToId(nx, ny, m);
if (findParent(ptId) != findParent(newPtId)) {
union_op(ptId, newPtId);
--cnt;
}
}
}
res.push_back(cnt);
}
return res;
}
bool IsInside(int x, int y, int n, int m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
int convertToId(int x, int y, int m) {
return x * m + y;
}
vector<int> father;
int findParent(int i) {
while (i != father[i]) {
i = father[i];
}
return i;
}
void union_op(int i, int j) {
int pi = findParent(i);
int pj = findParent(j);
if (pi != pj) {
father[pj] = pi;
}
}
};