disjoint set union 6ms solution


  • 0
    N

    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} };
    };
    

Log in to reply
 

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