Skip to content

Instantly share code, notes, and snippets.

@cashlo
Created August 21, 2018 08:47
Show Gist options
  • Save cashlo/f30fd6cfff257594db61c3a064451b9b to your computer and use it in GitHub Desktop.
Save cashlo/f30fd6cfff257594db61c3a064451b9b to your computer and use it in GitHub Desktop.
class Solution(object):
def numDistinctIslands(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def get_island(oi, oj, grid):
lands = []
def dfs(i, j, grid):
if i < 0 or j < 0: return
if i >= len(grid) or j >= len(grid[0]): return
if grid[i][j] == 0: return
grid[i][j] = 0
lands.append( (str(i-oi), str(j-oj)) )
dfs(i+1, j, grid)
dfs(i-1, j, grid)
dfs(i, j+1, grid)
dfs(i, j-1, grid)
dfs(oi, oj, grid)
return '|'.join([','.join(l) for l in lands])
count = 0
found_islands = {}
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell == 1:
# print i, j
island = get_island(i, j, grid)
if island not in found_islands:
found_islands[island] = 1
count += 1
# print found_islands
return count
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment