# BFS

```
class Solution(object):
def numDistinctIslands(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]: return 0
m,n=len(grid),len(grid[0])
# augment matrix to void length check
grid.append([0]*n)
for row in grid: row.append(0)
# BFS
def bfs(i0,j0):
grid[i0][j0]=-1
q=[(i0,j0)]
for i,j in q:
for I,J in (i-1,j),(i+1,j),(i,j-1),(i,j+1):
if grid[I][J]==1:
grid[I][J]=-1
q.append((I,J))
# generate relative position and covert to tuple
res.add(tuple((x-i0,y-j0) for x,y in q))
res=set()
for i in range(m):
for j in range(n):
if grid[i][j]==1:
bfs(i,j)
return len(res)
```