Leetcode 947 Most Stones Removed with Same Row or Column

发表于 |

在一个平面上，有一些点，每个点对应一个石头
现在，我们可以移除一个石头当且仅当这个石头的行或列上还存在着其他石头
现在给定所有石头的坐标，求我们最多能移除多少个石头。

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

思路分析：
碰到这种题一定要画图，实际模拟一下去除石头的过程，然后在其中寻找规律
首先我们来看这种情况

这种情况比较简单，显然我们只要保留A，那么其他所有的石头都能够被成功移除
OK，再来看这种情况

这种情况可能稍微有点难想到，我们仍然只需要保留A，就可以把其他所有石头成功移除，移除的顺序用数字标识了出来。实际上，不只是A，任意一个处于交叉点上的石头都和A等价。

那么我们发现了一个规律，对于一个连通的图，我们始终可以删除n-1个石头，其中n是这个连通图内的石头总数

我们使用dfs去找到这样的图，每次答案加上这次dfs遍历的石头数减一即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def removeStones(self, stones):
        stones = list(map(tuple, stones))
        s = set(stones)
        d = collections.defaultdict(list)
        for i,j in s:
            d[i].append(j)
            d[j].append(i)
        
        def dfs(i,j):
            for y in d[i]:
                if (i,y) not in s: continue
                s.remove((i,y))
                dfs(i,y)
            for x in d[j]:
                if (x,j) not in s: continue
                s.remove((x,j))
                dfs(x,j)
        
        n = len(s)
        res = 0
        for i,j in stones:
            if (i,j) not in s: continue
            s.remove((i,j))
            dfs(i,j)
            # n表示遍历之前集合s的长度
            # n-len(s)则表明这次dfs遍历的石头总数
            res += n - len(s) - 1
            n = len(s)
        return res