class Solution:
  
  def get_neigbors(self, matrix, i, j):
    neigbors = []
    up = (-1, 0, 'u')
    right = (0, 1, 'r')
    down = (1, 0, 'd')
    left = (0, -1, 'l')
    alpha = [up, right, down, left]
    for x, y, _dir in alpha:
      row = i + x
      col = j + y
      if row >= 0 and row < len(matrix) and col >= 0 and col < len(matrix[0]) and matrix[row][col] == 1:
        neigbors.append((row, col, _dir))
    return neigbors

  def dfs(self, matrix, i, j, path, all_paths, _dir):    
    if matrix[i][j] == 0:
      return 

    stack = [(i, j, _dir)]
    matrix[i][j] = 0 
    
    while stack:
      x, y, _dir = stack.pop()
      path.append(_dir)
      for row, col, direction in self.get_neigbors(matrix, x, y):
        stack.append((row, col, direction))
        matrix[row][col] = 0 
    
    all_paths.add(''.join(path))

  def findDistinctIslandsDFS(self, matrix):
    all_paths = set()
    for i in range(len(matrix)):
      for j in range(len(matrix[i])):
        self.dfs(matrix, i, j, [], all_paths, '#')

    print(all_paths)
    return len(all_paths)