# disjoint set union 6ms solution

• One more way to solve the problem.
Yes, it's an overkill J

``````class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) {
return 0;
}
Rows = board.size();
Cols = board[0].size();
vector<int> parent(Rows * Cols, 0);
vector<int> dsuRank(Rows * Cols, 0);
for (int i = 0; i < parent.size(); ++i) {
parent[i] = i;
}
for (int r1 = 0; r1 < Rows; ++r1) {
for (int c1 = 0; c1 < Cols; ++c1) {
if (board[r1][c1] == 'X') {
for (auto& shift : shifts) {
int r2 = r1 + shift.first;
int c2 = c1 + shift.second;
if (r2 < board.size() && c2 < board[0].size() && board[r2][c2] == 'X') {
unite(getIdx(r1, c1), getIdx(r2, c2), parent, dsuRank);
}
}
}
}
}
unordered_set<int> count;
for (int r = 0; r < Rows; ++r) {
for (int c = 0; c < Cols; ++c) {
if (board[r][c] == 'X') {
count.insert(find(getIdx(r, c), parent));
}
}
}
return count.size();
}
private:
int getIdx(int r, int c) {
return r * Cols + c;
}
int find(int x, vector<int>& parent) {
if (x != parent[x]) {
parent[x] = find(parent[x], parent);
}
return parent[x];
}
void unite(int x, int y, vector<int>& parent, vector<int>& rank) {
int px = find(x, parent);
int py = find(y, parent);
if (px != py) {
if (rank[px] < rank[py]) {
swap(px, py);
}
parent[py] = px;
if (rank[px] == rank[py]) {
rank[px] += 1;
}
}
}

int Rows = 0;
int Cols = 0;

vector<pair<int, int> > shifts = { {1, 0}, {0, 1} };
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.