Skip to content

947. Most Stones Removed with Same Row or Column

947. Most Stones Removed with Same Row or Column

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

难度: Medium

题意：

  1. 给平面上n个点
  2. 每次操作都可以挑选其中x坐标相等或者y坐标相等的两个点，划掉一个
  3. 求最多能划掉多少个

思路：

  • 我们平面上的点想象成图论上的一个几点，如果两个点之间，x坐标相等或者y坐标相等，那么连边
  • 题目就可以转为，求这个图的联通分量，因为只要两个团不联通，是无论如何无法进行操作的，所以剩下的个数必是联通分量的个数
  • 剩下就是dfs即可

解法：

class Solution {
public:
    bool flag[1010];
    void dfs(vector<vector<int>>& stones, int idx) {
        for (int i = 0;i < stones.size();i++) {
            if (flag[i]) {
                continue;
            }
            if (stones[idx][0] != stones[i][0] && stones[idx][1] != stones[i][1]) {
                continue;
            }
            flag[i] = true;
            dfs(stones, i);
        }
    }
    int removeStones(vector<vector<int>>& stones) {
        memset(flag, false, sizeof(flag));
        int ret = 0;
        for (int i = 0;i < stones.size();i++) {
            if (!flag[i]) {
                ret++;
                dfs(stones, i);
            }
        }
        return stones.size() - ret;
    }
};
回到顶部