947. Most Stones Removed with Same Row or Column

题目在这 https://leetcode.com/problems/mo ... same-row-or-column/
我想不太明白我这么做的TLE在哪，脑子混乱了突然间，希望大家能帮帮我！

I am trying to get all possible ways to remove stones.

1. class Solution:
   
2.     def removeStones(self, stones) -> int:
   
3.         row = collections.defaultdict(set)
   
4.         col = collections.defaultdict(set)
   
5.         for stone in stones:
   
6.             # so that row, col number i has these many stones
   
7.             row[stone[0]].add((stone[0], stone[1]))
   
8.             col[stone[1]].add((stone[0], stone[1]))
   
9.         self.res = 0
   
10. 
    
11.         def dfs(row, col, stones, remove):
    
12.             self.res = max(self.res, remove)
    
13.             for i in range(len(stones)):
    
14.                 stone = (stones[i][0], stones[i][1])
    
15.                 # check if the stone has been moved
    
16.                 if stone not in row[stone[0]] and stone not in col[stone[1]]:
    
17.                     continue
    
18.                 # if there are more than one stone in the same row or column
    
19.                 if len(row[stone[0]]) > 1 or len(col[stone[1]]) > 1:
    
20.                     removed_row = False
    
21.                     removed_col = False
    
22.                     # backtrack
    
23.                     if stone in row[stone[0]]:
    
24.                         row[stone[0]].remove(stone)
    
25.                         removed_row = True
    
26.                     if stone in col[stone[1]]:
    
27.                         col[stone[1]].remove(stone)
    
28.                         removed_col = True
    
29.                         
    
30.                     dfs(row, col, stones, remove + 1)
    
31. 
    
32.                     # backtrack
    
33.                     if removed_row:
    
34.                         row[stone[0]].add(stone)
    
35.                     if removed_col:
    
36.                         col[stone[1]].add(stone)
    
37. 
    
38.         dfs(row, col, stones, 0)
    
39.         return self.res

复制代码

一个2^N在N有1e4的时候当然会TLE..

Airtnp 发表于 2019-10-18 10:09
一个2^N在N有1e4的时候当然会TLE..

谢谢！能否解释一下为什么是2^N? 难道不是N^3 吗？对于每一个点，要经历n-1次的尝试，一共N个点，n^3?

这个题就是number of island的变种，4周相邻改成相同col或者row相邻就行了。Union find，DFS都行

Shen.TT 发表于 2019-10-18 11:09
这个题就是number of island的变种，4周相邻改成相同col或者row相邻就行了。Union find，DFS都行

是的我也看了答案，但就想知道我的原逻辑哪里出问题了

luciferth000 发表于 2019-10-18 10:55
谢谢！能否解释一下为什么是2^N? 难道不是N^3 吗？对于每一个点，要经历n-1次的尝试，一共N个点，n^3?

你写的逻辑是所有点都可以取或者不取。。。
T(n) = T(n-1)+T(n-2)+...T(1) + O(N^2)
哦不对你这个是N!...
T(n) = nT(n-1) +O(N^2)