forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
number-of-distinct-islands-ii.py
45 lines (40 loc) · 1.57 KB
/
number-of-distinct-islands-ii.py
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Time: O((m * n) * log(m * n))
# Space: O(m * n)
class Solution(object):
def numDistinctIslands2(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def dfs(i, j, grid, island):
if not (0 <= i < len(grid) and \
0 <= j < len(grid[0]) and \
grid[i][j] > 0):
return False
grid[i][j] *= -1
island.append((i, j))
for d in directions:
dfs(i+d[0], j+d[1], grid, island)
return True
def normalize(island):
shapes = [[] for _ in xrange(8)]
for x, y in island:
rotations_and_reflections = [[ x, y], [ x, -y], [-x, y], [-x, -y],
[ y, x], [ y, -x], [-y, x], [-y, -x]]
for i in xrange(len(rotations_and_reflections)):
shapes[i].append(rotations_and_reflections[i])
for shape in shapes:
shape.sort() # Time: O(ilogi), i is the size of the island, the max would be (m * n)
origin = list(shape[0])
for p in shape:
p[0] -= origin[0]
p[1] -= origin[1]
return min(shapes)
islands = set()
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
island = []
if dfs(i, j, grid, island):
islands.add(str(normalize(island)))
return len(islands)