# 947. Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a  move  consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

``````Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
``````

Example 2:

``````Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
``````

Example 3:

``````Input: stones = [[0,0]]
Output: 0
``````

Note:

1. `1 <= stones.length <= 1000`
2. `0 <= stones[i][j] < 10000`

``````class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
unordered_map<int, vector<int>> rowMap, colMap;
unordered_set<int> rowVisited;
int res = 0;
for (auto stone : stones) {
rowMap[stone[0]].push_back(stone[1]);
colMap[stone[1]].push_back(stone[0]);
}
for (auto a : rowMap) {
res += max(0, helper(rowMap, colMap, a.first, rowVisited) - 1);
}
return res;
}
int helper(unordered_map<int, vector<int>>& rowMap, unordered_map<int, vector<int>>& colMap, int row, unordered_set<int>& rowVisited) {
if (rowVisited.count(row)) return 0;
rowVisited.insert(row);
int res = rowMap[row].size();
for (int c : rowMap[row]) {
for (int r : colMap[c]) {
res += helper(rowMap, colMap, r, rowVisited);
}
}
return res;
}
};
``````

``````class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int cnt = 0, n = stones.size();
vector<int> root(n);
for (int i = 0; i < n; ++i) root[i] = i;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
root[getRoot(root, i)] = getRoot(root, j);
}
}
}
for (int i = 0; i < n; ++i) {
if (root[i] == i) ++cnt;
}
return n - cnt;
}
int getRoot(vector<int>& root, int x) {
return x == root[x] ? x : getRoot(root, root[x]);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/947

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197851/C%2B%2B-DFS

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/217790/C%2B%2B-union-find

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/discuss/197668/Count-the-Number-of-Islands-O(N)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation