leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0947.cpp (946B)

      1 class Solution {
      2   public:
      3     int removeStones(vector<vector<int>> &stones) {
      4         unordered_map<int, vector<int>> rows, cols;
      5         unordered_set<int> seen;
      6 
      7         for (int s = 0; s < size(stones); ++s)
      8             rows[stones[s][0]].push_back(s), cols[stones[s][1]].push_back(s);
      9 
     10         int c = 0;
     11         stack<int> st;
     12         for (int s = 0; s < size(stones); ++s) {
     13             if (seen.count(s)) continue;
     14             st.push(s);
     15             while (!st.empty()) {
     16                 int s = st.top();
     17                 st.pop();
     18                 if (seen.count(s)) continue;
     19                 seen.insert(s);
     20                 int r = stones[s][0], c = stones[s][1];
     21                 for (auto ss : rows[r])
     22                     if (!seen.count(ss)) st.push(ss);
     23                 for (auto ss : cols[c])
     24                     if (!seen.count(ss)) st.push(ss);
     25             }
     26             c++;
     27         }
     28 
     29         return size(stones) - c;
     30     }
     31 };