题目如下:
解题思路:题目解法本身不难,难点在于包了一个壳,去掉壳后就能看到本质了。本题的壳就是分组,把所有行相同或者列相同的元素分进同一个组,计算出一个有多少个组,删除操作完成后,每个组都会留下一个元素。最后的结果就是stones的个数减去组的个数。至于怎么求组的个数,DFS或者并查集都是可行的方法。我的解法是用DFS,最初用的是visit数组来保存元素是否遍历过,但是python语言会超时,只好改成每遍历完一个元素,都将其从stones中删除。
代码如下:
class Solution(object):
def removeStones(self, stones):
"""
:type stones: List[List[int]]
:rtype: int
"""
group = 0
original_len = len(stones)
while len(stones) > 0:
group += 1
queue = [(stones[0][0],stones[0][1])]
del stones[0]
while len(queue) > 0:
r, c = queue.pop(0)
inx_internal = 0
while inx_internal < len(stones):
if r == stones[inx_internal][0] or c == stones[inx_internal][1]:
queue.append((stones[inx_internal][0], stones[inx_internal][1]))
del stones[inx_internal]
else:
inx_internal += 1
return original_len - group