Solution: Problem Challenge 2

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))
        matr

    def findDistinctIslandsBit(self, matrix):
        if not matrix or not matrix[0]:
            return None
        # iterate over the matrix finding islands
        # dfs the island shifting the islands "code" based on the traversal
        # add the code int to a set, then return the size of the set
        # will use explicit stack dfs (for no particular reason)
        def dfsIsland(rowStart, colStart):
            code = 0
            stack = [(rowStart, colStart)]
            while stack:
                i, j = stack.pop()
                code <<= 1
                if not (0 <= i < n) or not (0 <= j < m):
                    continue
                code += matrix[i][j]
                if matrix[i][j]:
                    for diff in [-1, 1]:
                        s

Share a BFS version

from typing import List
from collections import deque


class Solution:

def numDistinctIslands(self, grid: List[List[int]]) -> int:
self.rows = len(grid)
self.cols = len(grid[0])
self.directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

island_pattern_set = set()

for x in range(self.rows):
for y in range(self.cols):
if grid[x][y] ==  1:
island_pattern = self.getIslandPattern(grid, x, y)
island_pattern_set.add(tuple(island_pattern))

return len(island_pattern_set)

def getIslandPattern(self, grid, ox, oy):
# BFS
island_pattern = list()
neighbors = deque()
neighbors.append((ox, oy))
while neighbors:
x, y = neighbors.popleft()
# add relative position to the pattern
island_pattern.append((x - ox, y - oy))
grid[x][y] = 0 # mark visited
for ix, iy in self.directions:
nx,