Given a boolean 2D matrix grid of size n * m. You have to find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be distinct if and only if one island is not equal to another (not rotated or reflected).
Example 1:
Input:
grid[][] = {{1, 1, 0, 0, 0},
            {1, 1, 0, 0, 0},
            {0, 0, 0, 1, 1},
            {0, 0, 0, 1, 1}}
Output:
1
Explanation:
grid[][] = {{1, 1, 0, 0, 0}, 
            {1, 1, 0, 0, 0}, 
            {0, 0, 0, 1, 1}, 
            {0, 0, 0, 1, 1}}
Same colored islands are equal.
We have 2 equal islands, so we 
have only 1 distinct island.
Example 2:
Input:
grid[][] = {{1, 1, 0, 1, 1},
            {1, 0, 0, 0, 0},
            {0, 0, 0, 0, 1},
            {1, 1, 0, 1, 1}}
Output:
3
Explanation:
grid[][] = {{1, 1, 0, 1, 1}, 
            {1, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 1}, 
            {1, 1, 0, 1, 1}}
Same colored islands are equal.
We have 4 islands, but 2 of them
are equal, So we have 3 distinct islands.
Your Task:
You don't need to read or print anything. Your task is to complete the function countDistinctIslands() which takes the grid as an input parameter and returns the total number of distinct islands.
Expected Time Complexity: O(n * m)
Expected Space Complexity: O(n * m)
Constraints:
1 ≤ n, m ≤ 500
grid[i][j] == 0 or grid[i][j] == 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



import sys

from typing import List

sys.setrecursionlimit(10**8)

class Solution:

    def countDistinctIslands(self, grid : List[List[int]]) -> int:

        # code here

Solutions:
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		vis = []
		res = set()
		for i in range(m):
			vis.append([False] * n)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1 and vis[i][j] == False:
					l = []
					self.dfs(i, j, grid, vis, l, i, j)
					res.add(str(l))
		return len(res)

	def dfs(self, i, j, grid, vis, l, row0, col0):
		m = len(grid)
		n = len(grid[0])
		if i - 1 >= 0 and j >= 0 and (grid[i - 1][j] == 1) and (vis[i - 1][j] == False):
			vis[i - 1][j] = True
			l.append([i - 1 - row0, j - col0])
			self.dfs(i - 1, j, grid, vis, l, row0, col0)
		if i >= 0 and j - 1 >= 0 and (grid[i][j - 1] == 1) and (vis[i][j - 1] == False):
			vis[i][j - 1] = True
			l.append([i - row0, j - 1 - col0])
			self.dfs(i, j - 1, grid, vis, l, row0, col0)
		if i + 1 <= m - 1 and j <= n - 1 and (grid[i + 1][j] == 1) and (vis[i + 1][j] == False):
			vis[i + 1][j] = True
			l.append([i + 1 - row0, j - col0])
			self.dfs(i + 1, j, grid, vis, l, row0, col0)
		if i <= m - 1 and j + 1 <= n - 1 and (grid[i][j + 1] == 1) and (vis[i][j + 1] == False):
			vis[i][j + 1] = True
			l.append([i - row0, j + 1 - col0])
			self.dfs(i, j + 1, grid, vis, l, row0, col0)


import sys
from typing import List
import itertools
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, row: int, col: int, vis: List[List[int]], grid: List[List[int]], vec, row0: int, col0: int) -> None:
		vis[row][col] = 1
		vec.append((row - row0, col - col0))
		n = len(grid)
		m = len(grid[0])
		delrow = [-1, 0, 1, 0]
		delcol = [0, -1, 0, 1]
		for i in range(4):
			nrow = row + delrow[i]
			ncol = col + delcol[i]
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (not vis[nrow][ncol]) and (grid[nrow][ncol] == 1):
				self.dfs(nrow, ncol, vis, grid, vec, row0, col0)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for _ in range(n)]
		st = set()
		for i in range(n):
			for j in range(m):
				if not vis[i][j] and grid[i][j] == 1:
					vec = []
					self.dfs(i, j, vis, grid, vec, i, j)
					st.add(tuple(vec))
		return len(st)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)
import queue

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		s = queue.Queue()
		n = len(grid)
		m = len(grid[0])
		vis = []
		for i in range(n):
			v = []
			for j in range(m):
				v.append(0)
			vis.append(v)
		res = set()
		row_dir = [-1, 0, 1, 0]
		col_dir = [0, -1, 0, 1]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					s.put([i, j])
					ans = []
					while not s.empty():
						curr = s.get()
						for d in range(4):
							x = curr[0] + row_dir[d]
							y = curr[1] + col_dir[d]
							if x >= 0 and x < n and (y >= 0) and (y < m) and (grid[x][y] == 1) and (vis[x][y] == 0):
								s.put([x, y])
								vis[x][y] = 1
								t = x - i
								t1 = y - j
								ans.append((t, t1))
					res.add(tuple(ans))
		return len(res)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(row, col) = (len(grid), len(grid[0]))
		visited = [[0 for _ in range(col)] for _ in range(row)]
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		ans = set()

		def dfs(x, y, i, j, temp):
			nonlocal visited, drow, dcol, row, col
			visited[i][j] = 1
			temp.append((i - x, j - y))
			for k in range(0, 4):
				nrow = i + drow[k]
				ncol = j + dcol[k]
				if nrow >= 0 and nrow < row and (ncol >= 0) and (ncol < col) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					dfs(x, y, nrow, ncol, temp)
		for i in range(row):
			for j in range(col):
				if not visited[i][j] and grid[i][j] == 1:
					temp = []
					dfs(i, j, i, j, temp)
					ans.add(tuple(temp))
		return len(ans)


import sys
from typing import List
import collections
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		islands = {}
		cur_island = ''
		(m, n) = (len(grid), len(grid[0]))
		queue = collections.deque([])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					queue.append([i, j])
					grid[i][j] = 0
					while queue:
						(x, y) = queue.popleft()
						cur_island += '{},{};'.format(x - i, y - j)
						if x > 0 and grid[x - 1][y] == 1:
							queue.append([x - 1, y])
							grid[x - 1][y] = 0
						if y > 0 and grid[x][y - 1] == 1:
							queue.append([x, y - 1])
							grid[x][y - 1] = 0
						if x < m - 1 and grid[x + 1][y] == 1:
							queue.append([x + 1, y])
							grid[x + 1][y] = 0
						if y < n - 1 and grid[x][y + 1] == 1:
							queue.append([x, y + 1])
							grid[x][y + 1] = 0
					if cur_island not in islands:
						islands[cur_island] = True
					cur_island = ''
		return len(islands.keys())


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for _ in range(m)] for _ in range(n)]
		vecPair = set()

		def dfs(row, col, row0, col0, vec):
			vis[row][col] = 1
			vec += (row - row0, col - col0)
			for (delrow, delcol) in ([-1, 0], [0, 1], [1, 0], [0, -1]):
				nrow = row + delrow
				ncol = col + delcol
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] != 1) and (grid[nrow][ncol] == 1):
					vec = dfs(nrow, ncol, row0, col0, vec)
			return vec
		for i in range(n):
			for j in range(m):
				if vis[i][j] != 1 and grid[i][j] == 1:
					vec = ()
					vec = dfs(i, j, i, j, vec)
					vecPair.add(vec)
		return len(vecPair)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(row, col, row1, col1, s):
			grid[row][col] = 0
			s.append(tuple([row - row1, col - col1]))
			dirx = [-1, 1, 0, 0]
			diry = [0, 0, -1, 1]
			for ele in range(4):
				newx = row + dirx[ele]
				newy = col + diry[ele]
				if newx in range(len(grid)) and newy in range(len(grid[0])) and (grid[newx][newy] == 1):
					dfs(newx, newy, row1, col1, s)
		setter = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					s = []
					dfs(i, j, i, j, s)
					setter.add(tuple(s))
		return len(setter)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for i in range(m)] for j in range(n)]

		def dfs(row, col, visited, grid, row0, col0, island):
			visited[row][col] = 1
			island.append((row - row0, col - col0))
			drow = [-1, 0, +1, 0]
			dcol = [0, -1, 0, +1]
			for i in range(4):
				nrow = row + drow[i]
				ncol = col + dcol[i]
				if ncol < m and nrow < n and (ncol > -1) and (nrow > -1) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					visited[nrow][ncol] = 1
					island.append((row - nrow, col - ncol))
					dfs(nrow, ncol, visited, grid, row0, col0, island)
		list_of_island = []
		for r in range(n):
			for c in range(m):
				if visited[r][c] == 0 and grid[r][c] == 1:
					island = []
					dfs(r, c, visited, grid, r, c, island)
					list_of_island.append(island)
		tmp = []
		for i in list_of_island:
			if i not in tmp:
				tmp.append(i)
		return len(tmp)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		ans = set()

		def dfs(r, c, curr, rBase, cBase):
			if r < 0 or r >= n or c < 0 or (c >= m) or (grid[r][c] == 0):
				return
			grid[r][c] -= 1
			curr.append((r - rBase, c - cBase))
			dfs(r + 1, c, curr, rBase, cBase)
			dfs(r - 1, c, curr, rBase, cBase)
			dfs(r, c + 1, curr, rBase, cBase)
			dfs(r, c - 1, curr, rBase, cBase)
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					curr = []
					dfs(i, j, curr, i, j)
					ans.add(tuple(curr))
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

		def dfs(row, col, vis, lst, bRow, bCol):
			vis[row][col] = 1
			lst.append((row - bRow, col - bCol))
			for (x, y) in directions:
				(nrow, ncol) = (row + x, col + y)
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					dfs(nrow, ncol, vis, lst, bRow, bCol)
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for _ in range(m)] for _ in range(n)]
		st = set()
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and grid[i][j] == 1:
					lst = []
					dfs(i, j, vis, lst, i, j)
					st.add(tuple(lst))
		return len(st)


from collections import deque
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = set()
		ans = set()

		def bsf(row, col, vis, grid):
			q = deque([])
			q.append((row, col))
			vis.add((row, col))
			new = ()
			while q:
				(r, c) = q.popleft()
				new = new + (r - r, c - c)
				dRow = [-1, 1, 0, 0]
				dCol = [0, 0, -1, 1]
				for i in range(4):
					nr = r + dRow[i]
					nc = c + dCol[i]
					if 0 <= nr < n and 0 <= nc < m and (grid[nr][nc] == 1) and ((nr, nc) not in vis):
						vis.add((nr, nc))
						q.append((nr, nc))
						new = new + (nr - r, nc - c)
			ans.add(new)
		for l in range(n):
			for k in range(m):
				if grid[l][k] == 1 and (l, k) not in vis:
					bsf(l, k, vis, grid)
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, a: List[List[int]]) -> int:
		ans = set()
		n = len(a)
		m = len(a[0])
		for i in range(n):
			for j in range(m):
				if a[i][j] == 1:
					temp = ''
					q = [(i, j)]
					while q:
						(row, col) = q.pop(0)
						a[row][col] = 0
						if row + 1 >= 0 and row + 1 < n and (a[row + 1][col] == 1):
							a[row + 1][col] = 0
							temp = temp + 'D'
							q.append((row + 1, col))
						else:
							temp = temp + 'E'
						if row - 1 >= 0 and row - 1 < n and (a[row - 1][col] == 1):
							a[row - 1][col] = 0
							temp = temp + 'U'
							q.append((row - 1, col))
						else:
							temp = temp + 'E'
						if col + 1 >= 0 and col + 1 < m and (a[row][col + 1] == 1):
							a[row][col + 1] = 0
							temp = temp + 'R'
							q.append((row, col + 1))
						else:
							temp = temp + 'E'
						if col - 1 >= 0 and col - 1 < m and (a[row][col - 1] == 1):
							a[row][col - 1] = 0
							temp = temp + 'L'
							q.append((row, col - 1))
						else:
							temp = temp + 'E'
					ans.add(temp)
		return len(ans)


import sys
from typing import List
from array import *
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, row, col, grid, vis, ls, row0, col0, n, m):
		vis[row][col] = 1
		ls.append((row - row0, col - col0))
		drow = [0, +1, 0, -1]
		dcol = [+1, 0, -1, 0]
		for i in range(4):
			nrow = row + drow[i]
			ncol = col + dcol[i]
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (not vis[nrow][ncol]) and (grid[nrow][ncol] == 1):
				Solution.dfs(self, nrow, ncol, grid, vis, ls, row0, col0, n, m)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for i in range(n)]
		st = set()
		for i in range(n):
			for j in range(m):
				if not vis[i][j] and grid[i][j] == 1:
					ls = []
					Solution.dfs(self, i, j, grid, vis, ls, i, j, n, m)
					st.add(tuple(ls))
		return len(st)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		r = len(grid)
		c = len(grid[0])

		def dfs(curX, curY, ky: list):
			grid[curX][curY] = 0
			if curX - 1 >= 0 and grid[curX - 1][curY] == 1:
				ky.append('U')
				ky = dfs(curX - 1, curY, ky)
			if curY + 1 < c and grid[curX][curY + 1] == 1:
				ky.append('R')
				ky = dfs(curX, curY + 1, ky)
			if curX + 1 < r and grid[curX + 1][curY] == 1:
				ky.append('D')
				ky = dfs(curX + 1, curY, ky)
			if curY - 1 >= 0 and grid[curX][curY - 1] == 1:
				ky.append('L')
				ky = dfs(curX, curY - 1, ky)
			ky.append('B')
			return ky
		hsh = set()
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 1:
					ky = dfs(i, j, [])
					hsh.add(str(ky))
		return len(hsh)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(r, c, grid, visi, vec, row, col):
			visi[r][c] = 1
			vec.append([r - row, c - col])
			for (i, j) in ([0, 1], [0, -1], [-1, 0], [1, 0]):
				nr = r + i
				nc = c + j
				if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (not visi[nr][nc]) and (grid[nr][nc] == 1):
					dfs(nr, nc, grid, visi, vec, row, col)
		n = len(grid)
		m = len(grid[0])
		visi = [[0] * m for _ in range(n)]
		ans = []
		for i in range(n):
			for j in range(m):
				if not visi[i][j] and grid[i][j] == 1:
					vec = []
					dfs(i, j, grid, visi, vec, i, j)
					if vec not in ans:
						ans.append(vec)
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		row = len(grid)
		col = len(grid[0])

		def dfs(i, j, tmp, r, c):
			if i >= row or i < 0 or j >= col or (j < 0):
				return
			if visited[i][j] or grid[i][j] == 0:
				return
			visited[i][j] = 1
			tmp.append((i - r, j - c))
			dfs(i - 1, j, tmp, r, c)
			dfs(i, j - 1, tmp, r, c)
			dfs(i + 1, j, tmp, r, c)
			dfs(i, j + 1, tmp, r, c)
		visited = [[0 for _ in range(col)] for _ in range(row)]
		res = set()
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1 and visited[i][j] == 0:
					tmp = []
					dfs(i, j, tmp, i, j)
					if tmp:
						res.add(tuple(tmp.copy()))
		return len(res)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		visited = [[0 for i in range(n)] for j in range(m)]
		directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
		distictset = set()

		def dfs(i, j, basei, basej, temp):
			visited[i][j] = 1
			temp.append((i - basei, j - basej))
			for (dx, dy) in directions:
				(x, y) = (i + dx, j + dy)
				if x >= 0 and x < m and (y >= 0) and (y < n) and (visited[x][y] == 0) and (grid[x][y] == 1):
					dfs(x, y, basei, basej, temp)
		for i in range(m):
			for j in range(n):
				if visited[i][j] == 0 and grid[i][j] == 1:
					temp = []
					dfs(i, j, i, j, temp)
					distictset.add(tuple(temp))
		return len(distictset)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		s = set()
		visited = set()

		def dfs(i, j, vec, brow, bcol):
			if 0 <= i < m and 0 <= j < n and grid[i][j] and ((i, j) not in visited):
				visited.add((i, j))
				vec.append((i - brow, j - bcol))
				directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
				for (u, v) in directions:
					dfs(i + u, j + v, vec, brow, bcol)
		for i in range(m):
			for j in range(n):
				if (i, j) not in visited and grid[i][j]:
					vec = []
					dfs(i, j, vec, i, j)
					s.add(tuple(vec))
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, r, c, grid, vis, n, m, vec, row0, col0):
		vis[r][c] = True
		vec.append([r - row0, c - col0])
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		for i in range(4):
			nr = r + dr[i]
			nc = c + dc[i]
			if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (grid[nr][nc] == 1) and (vis[nr][nc] == False):
				self.dfs(nr, nc, grid, vis, n, m, vec, row0, col0)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[False for i in range(m)] for i in range(n)]
		hs = set()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == False:
					vec = []
					self.dfs(i, j, grid, vis, n, m, vec, i, j)
					hs.add(str(vec))
		return len(hs)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, row, col, visited, grid, vec, row0, col0, m, n):
		visited[row][col] = 1
		vec.append((row - row0, col - col0))
		delta_col = [-1, 0, 1, 0]
		delta_row = [0, 1, 0, -1]
		for i in range(0, 4):
			nrow = row + delta_row[i]
			ncol = col + delta_col[i]
			if nrow >= 0 and nrow < m and (ncol >= 0) and (ncol < n) and (grid[nrow][ncol] == 1) and (not visited[nrow][ncol]):
				self.dfs(nrow, ncol, visited, grid, vec, row0, col0, m, n)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		visited = [[False for i in range(0, n)] for j in range(0, m)]
		island = set()
		for i in range(0, m):
			for j in range(0, n):
				if not visited[i][j] and grid[i][j] == 1:
					vec = []
					self.dfs(i, j, visited, grid, vec, i, j, m, n)
					island.add(tuple(vec))
		return len(island)


from collections import deque
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		r = len(grid)
		c = len(grid[0])
		setty = set()
		visited = [[0] * c for i in range(r)]
		for i in range(r):
			for j in range(c):
				if not visited[i][j] and grid[i][j] == 1:
					arr = []
					visited[i][j] = 1
					self.bfs(i, j, visited, grid, i, j, arr)
					setty.add(tuple(arr))
		return len(setty)

	def bfs(self, row0, col0, visited, grid, row, col, arr):
		q = deque()
		q.append([row, col])
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		while q:
			n = q.popleft()
			r = n[0]
			c = n[1]
			arr.append((row0 - r, col0 - c))
			for i in range(4):
				nrow = r + drow[i]
				ncol = c + dcol[i]
				if nrow >= 0 and nrow < len(grid) and (ncol >= 0) and (ncol < len(grid[0])) and (not visited[nrow][ncol]) and (grid[nrow][ncol] == 1):
					visited[nrow][ncol] = 1
					q.append([nrow, ncol])


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		r = len(grid)
		c = len(grid[0])
		setty = set()
		visited = [[0] * c for i in range(r)]
		for i in range(r):
			for j in range(c):
				if not visited[i][j] and grid[i][j] == 1:
					arr = []
					self.dfs(i, j, visited, grid, i, j, arr)
					setty.add(tuple(arr))
		return len(setty)

	def dfs(self, row0, col0, visited, grid, row, col, arr):
		visited[row][col] = 1
		arr.append(tuple([row - row0, col - col0]))
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		for i in range(4):
			nrow = row + drow[i]
			ncol = col + dcol[i]
			if nrow >= 0 and nrow < len(grid) and (ncol >= 0) and (ncol < len(grid[0])) and (not visited[nrow][ncol]) and (grid[nrow][ncol] == 1):
				self.dfs(row0, col0, visited, grid, nrow, ncol, arr)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def is_safe(self, i, j, g):
		if i >= 0 and j >= 0 and (i < len(g)) and (j < len(g[i])) and (g[i][j] == 1) and ((i, j) not in self.vis):
			return True
		return False

	def countDistinctIslands(self, g) -> int:
		ans = {}
		adj = {}
		self.vis = {}
		q = []
		for i in range(0, len(g)):
			for j in range(0, len(g[i])):
				if g[i][j] == 0 or (i, j) in self.vis:
					continue
				l = []
				q.append((i, j))
				self.vis[i, j] = (i, j)
				while len(q) != 0:
					q_size = len(q)
					while q_size != 0:
						q_size -= 1
						(ii, jj) = q.pop(0)
						l.append((ii - i, jj - j))
						if self.is_safe(ii + 1, jj, g):
							q.append((ii + 1, jj))
							self.vis[ii + 1, jj] = (ii, jj)
						if self.is_safe(ii - 1, jj, g):
							q.append((ii - 1, jj))
							self.vis[ii - 1, jj] = (ii, jj)
						if self.is_safe(ii, jj + 1, g):
							q.append((ii, jj + 1))
							self.vis[ii, jj + 1] = (ii, jj)
						if self.is_safe(ii, jj - 1, g):
							q.append((ii, jj - 1))
							self.vis[ii, jj - 1] = (ii, jj)
				ans[tuple(l)] = None
		return len(ans)


import sys
from typing import List, Tuple
sys.setrecursionlimit(10 ** 8)

class Solution:

	def __dfs__(self, grid: list, visited: list, row: int, col: int, n: int, m: int, path: List[Tuple], start_row: int, start_col: int):
		visited[row][col] = True
		path.append((row - start_row, col - start_col))
		adjacent_nodes = [(row, col - 1), (row, col + 1), (row - 1, col), (row + 1, col)]
		for (temp_row, temp_col) in adjacent_nodes:
			if n > temp_row >= 0 and 0 <= temp_col < m and (not visited[temp_row][temp_col]) and (grid[temp_row][temp_col] != 0):
				self.__dfs__(grid, visited, temp_row, temp_col, n, m, path, start_row, start_col)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(size_n, size_m) = (len(grid), len(grid[0]))
		if not grid or size_n == 0:
			return 0
		visited = [[False for _ in range(size_m)] for _ in grid]
		s = set()
		for row in range(size_n):
			for col in range(size_m):
				if not visited[row][col] and grid[row][col] != 0:
					path = list()
					self.__dfs__(grid, visited, row, col, size_n, size_m, path, row, col)
					path = tuple(path)
					s.add(path)
		return len(s)


import sys
from typing import List
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		vis = [[0] * m for _ in range(n)]
		q = deque()
		s = []
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					q.append((i, j))
					vis[i][j] = 1
					temp = []
					while q:
						(x, y) = q.popleft()
						temp.append((x - i, y - j))
						(dx, dy) = ([1, 0, -1, 0], [0, -1, 0, 1])
						for k in range(4):
							(nx, ny) = (x + dx[k], y + dy[k])
							if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (vis[nx][ny] == 0) and (grid[nx][ny] == 1):
								vis[nx][ny] = 1
								q.append((nx, ny))
					if temp not in s:
						s.append(temp)
		return len(s)


import sys
from typing import List
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		queue = deque()
		vis = [[0 for _ in range(m)] for _ in range(n)]
		s = set()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					self.island = ''
					self.dfs(i, j, i, j, vis, grid)
					s.add(self.island)
					self.island = ''
		return len(s)

	def dfs(self, row, col, R, C, vis, grid):
		drow = row - R
		dcol = col - C
		self.island += str(drow) + str(dcol)
		vis[row][col] = 1
		for (x, y) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
			nrow = row + x
			ncol = col + y
			if 0 <= nrow < n and 0 <= ncol < m and (vis[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
				self.dfs(nrow, ncol, R, C, vis, grid)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		if len(grid) <= 1 and len(grid[0]) <= 1:
			return grid[0][0]
		import numpy as np
		ab = len(grid)
		ba = len(grid[0])
		vis = np.zeros((ab, ba))
		s = []
		q = []
		c = 0
		drow = [-1, 0, 0, 1]
		dcol = [0, 1, -1, 0]
		for i in range(ab):
			for j in range(ba):
				if grid[i][j] == 1 and vis[i][j] != 1:
					x = []
					c += 1
					q.append((i, j))
					vis[i][j] = 1
					b_r = i
					b_c = j
					while q != []:
						row = q[0][0]
						col = q[0][1]
						for l in range(4):
							n_r = row + drow[l]
							n_c = col + dcol[l]
							if n_r >= 0 and n_r <= ab - 1 and (n_c >= 0) and (n_c <= ba - 1) and (grid[n_r][n_c] == 1) and (vis[n_r][n_c] != 1):
								q.append((n_r, n_c))
								vis[n_r][n_c] = 1
						x.append((b_r - row, b_c - col))
						q.pop(0)
					s.append(x)
		w = []
		for i in s:
			if i not in w:
				w.append(i)
		return len(w)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, i, j, visited, grid, basei, basej, arr):
		arr.append((basei - i, basej - j))
		visited[i][j] = 1
		if i - 1 >= 0 and visited[i - 1][j] == 0 and (grid[i - 1][j] == 1):
			visited[i - 1][j] = 1
			self.dfs(i - 1, j, visited, grid, basei, basej, arr)
		if i + 1 < len(grid) and visited[i + 1][j] == 0 and (grid[i + 1][j] == 1):
			visited[i + 1][j] = 1
			self.dfs(i + 1, j, visited, grid, basei, basej, arr)
		if j - 1 >= 0 and visited[i][j - 1] == 0 and (grid[i][j - 1] == 1):
			visited[i][j - 1] = 1
			self.dfs(i, j - 1, visited, grid, basei, basej, arr)
		if j + 1 < len(grid[0]) and visited[i][j + 1] == 0 and (grid[i][j + 1] == 1):
			visited[i][j + 1] = 1
			self.dfs(i, j + 1, visited, grid, basei, basej, arr)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		visited = []
		for i in range(n):
			arr = []
			for j in range(m):
				arr.append(0)
			visited.append(arr)
		ans = set()
		for i in range(n):
			for j in range(m):
				if visited[i][j] == 0 and grid[i][j] == 1:
					arr = []
					self.dfs(i, j, visited, grid, i, j, arr)
					ans.add(tuple(arr))
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		s_set = set()

		def find(grid, i, j, k, l, arr):
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (grid[i][j] == 0):
				return
			if grid[i][j] == 1:
				arr.append((k, l))
				grid[i][j] = 0
				find(grid, i, j + 1, k, l + 1, arr)
				find(grid, i, j - 1, k, l - 1, arr)
				find(grid, i + 1, j, k + 1, l, arr)
				find(grid, i - 1, j, k - 1, l, arr)
			return arr
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					a = find(grid, i, j, 0, 0, [])
					if a:
						t = tuple(a)
						s_set.add(t)
		return len(s_set)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = set()
		coord = []
		res = set()

		def dfs(r, c):
			if r < 0 or c < 0 or r >= len(grid) or (c >= len(grid[0])) or (grid[r][c] == 0) or ((r, c) in visited):
				return
			visited.add((r, c))
			coord.append((r - sr, c - sc))
			dfs(r + 1, c)
			dfs(r - 1, c)
			dfs(r, c + 1)
			dfs(r, c - 1)
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				sr = r
				sc = c
				coord = []
				if (r, c) not in visited and grid[r][c] == 1:
					dfs(r, c)
					res.add(tuple(coord))
		return len(res)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		visited = [[False] * m for _ in range(n)]
		visited_shape = set()

		def dfs(i, j, temp, basei, basej):
			visited[i][j] = True
			nrow = i - basei
			ncol = j - basej
			temp.append((nrow, ncol))
			for (ni, nj) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= ni < n and 0 <= nj < m and (not visited[ni][nj]) and (grid[ni][nj] == 1):
					dfs(ni, nj, temp, basei, basej)
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not visited[i][j]):
					temp = []
					dfs(i, j, temp, i, j)
					visited_shape.add(tuple(temp))
		return len(visited_shape)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def bfs(self, i, j, visited, grid):
		m = len(grid)
		n = len(grid[0])
		visited[i][j] = 1
		temp = []
		temp.append([i, j])
		result = temp.copy()
		while temp:
			x = temp.pop(0)
			i = x[0]
			j = x[1]
			if i > 0 and grid[i - 1][j] == 1 and (visited[i - 1][j] == -1):
				temp.append([i - 1, j])
				result.append([i - 1, j])
				visited[i - 1][j] = 1
			if j < n - 1 and grid[i][j + 1] == 1 and (visited[i][j + 1] == -1):
				temp.append([i, j + 1])
				result.append([i, j + 1])
				visited[i][j + 1] = 1
			if i < m - 1 and grid[i + 1][j] == 1 and (visited[i + 1][j] == -1):
				temp.append([i + 1, j])
				result.append([i + 1, j])
				visited[i + 1][j] = 1
			if j > 0 and grid[i][j - 1] == 1 and (visited[i][j - 1] == -1):
				temp.append([i, j - 1])
				result.append([i, j - 1])
				visited[i][j - 1] = 1
		for i in result:
			temp.append(tuple([i[0] - result[0][0], i[1] - result[0][1]]))
		return temp

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		visited = []
		for i in range(m):
			temp = [-1] * n
			visited.append(temp)
		result = set()
		for i in range(m):
			for j in range(n):
				if visited[i][j] == -1 and grid[i][j] == 1:
					z = self.bfs(i, j, visited, grid)
					result.add(tuple(z))
		return len(result)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, grid, visited, row, col, temp):
		if 0 <= row < len(grid) and 0 <= col < len(grid[0]) and grid[row][col] and visited[row][col]:
			visited[row][col] = 0
			temp.append((row, col))
			self.dfs(grid, visited, row - 1, col, temp)
			self.dfs(grid, visited, row + 1, col, temp)
			self.dfs(grid, visited, row, col - 1, temp)
			self.dfs(grid, visited, row, col + 1, temp)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = grid.copy()
		result = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] and visited[i][j]:
					temp = []
					self.dfs(grid, visited, i, j, temp)
					result.add(tuple(((x - i, y - j) for (x, y) in temp)))
		return len(result)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		s = set()
		visited = [[0 for i in range(len(grid[0]))] for i in range(len(grid))]

		def bfs(i, j):
			queue = []
			queue.append((i, j))
			visited[i][j] = 1
			(rooti, rootj) = (i, j)
			shape = []
			while len(queue) != 0:
				(i, j) = queue.pop(0)
				shape.append((i, j))
				if not j - 1 < 0 and grid[i][j - 1] == 1 and (visited[i][j - 1] != 1):
					queue.append((i, j - 1))
					visited[i][j - 1] = 1
				if not i - 1 < 0 and grid[i - 1][j] == 1 and (visited[i - 1][j] != 1):
					queue.append((i - 1, j))
					visited[i - 1][j] = 1
				if not i + 1 >= len(grid) and grid[i + 1][j] == 1 and (visited[i + 1][j] != 1):
					queue.append((i + 1, j))
					visited[i + 1][j] = 1
				if not j + 1 >= len(grid[0]) and grid[i][j + 1] == 1 and (visited[i][j + 1] != 1):
					queue.append((i, j + 1))
					visited[i][j + 1] = 1
			for k in range(len(shape)):
				shape[k] = (shape[k][0] - rooti, shape[k][1] - rootj)
			return shape
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and visited[i][j] != 1:
					s.add(tuple(bfs(i, j)))
				else:
					visited[i][j] = 1
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, si, sj, i, j, grid, vis, arr, dr, dc, n, m):
		vis[i][j] = 1
		arr.append((i - si, j - sj))
		for k in range(4):
			r = i + dr[k]
			c = j + dc[k]
			if r >= 0 and c >= 0 and (r < n) and (c < m) and (vis[r][c] == 0) and (grid[r][c] == 1):
				self.dfs(si, sj, r, c, grid, vis, arr, dr, dc, n, m)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		st = set()
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		vis = [[0 for j in range(m)] for i in range(n)]
		res = 0
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and grid[i][j] == 1:
					arr = []
					self.dfs(i, j, i, j, grid, vis, arr, dr, dc, n, m)
					if tuple(arr) not in st:
						st.add(tuple(arr))
						res += 1
		return res


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])

		def dfs(x, y, i, j, v):
			dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]]
			if i < 0 or i >= n or j < 0 or (j >= m) or (grid[i][j] <= 0):
				return
			grid[i][j] = -1
			v.append((i - x, j - y))
			for dir in dirs:
				dfs(x, y, i + dir[0], j + dir[1], v)
		coor = set()
		for i in range(n):
			for j in range(m):
				if grid[i][j] != 1:
					continue
				v = []
				dfs(i, j, i, j, v)
				coor.add(tuple(v))
		return len(coor)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, grid, m, n, i, j, ls, basex, basey):
		ls.append((i - basex, j - basey))
		grid[i][j] = 0
		dx = [-1, 0, 1, 0]
		dy = [0, 1, 0, -1]
		for k in range(4):
			nx = i + dx[k]
			ny = j + dy[k]
			if nx >= 0 and ny >= 0 and (nx < m) and (ny < n) and (grid[nx][ny] == 1):
				self.dfs(grid, m, n, nx, ny, ls, basex, basey)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		st = set()
		ls = []
		for i in range(m):
			for j in range(n):
				ls = []
				if grid[i][j] == 1:
					self.dfs(grid, m, n, i, j, ls, i, j)
					st.add(tuple(ls))
		return len(st)


from collections import deque
from math import inf
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		st = set()
		dirx = [[0, 1], [0, -1], [1, 0], [-1, 0]]

		def isvalid(i, j):
			if i >= 0 and j >= 0 and (i < len(grid)) and (j < len(grid[0])) and (grid[i][j] == 1):
				return True
			return False
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					temp = []
					mini = i
					minj = j
					dq = [[i, j]]
					while dq:
						(x, y) = dq.pop()
						temp.append((x - mini, y - minj))
						grid[x][y] = 0
						for (dx, dy) in dirx:
							if isvalid(x + dx, y + dy):
								dq.append([x + dx, y + dy])
					st.add(tuple(temp))
		return len(st)


import sys
from typing import List
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(num_rows, num_cols) = (len(grid), len(grid[0]))
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		visited = set()
		num_unique_islands = set()

		def is_valid(ro, co, visited, num_rows, num_cols, grid):
			if ro < 0 or ro > num_rows - 1 or co < 0 or (co > num_cols - 1) or ((ro, co) in visited) or (grid[ro][co] == 0):
				return False
			return True

		def bfs(ro, co, visited, grid, directions):
			visited.add((ro, co))
			q = deque()
			q.append((ro, co))
			bfs_li = []
			while q:
				(front_ro, front_co) = q.popleft()
				bfs_li.append((front_ro, front_co))
				for (incre_ro, incre_co) in directions:
					(new_ro, new_co) = (front_ro + incre_ro, front_co + incre_co)
					if is_valid(new_ro, new_co, visited, num_rows, num_cols, grid):
						q.append((new_ro, new_co))
						visited.add((new_ro, new_co))
			return bfs_li

		def get_rel_coords(bfs_li):
			out = ()
			base_coord = bfs_li[0]
			for each_coord in bfs_li:
				(new_coord_x, new_coord_y) = (-base_coord[0] + each_coord[0], -base_coord[1] + each_coord[1])
				out = out + (new_coord_x, new_coord_y)
			return out
		for ro in range(num_rows):
			for co in range(num_cols):
				if (ro, co) not in visited and grid[ro][co] == 1:
					bfs_li = bfs(ro, co, visited, grid, directions)
					num_unique_islands.add(get_rel_coords(bfs_li))
		return len(num_unique_islands)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		res = []

		def traverse(i, j, grid, res):
			m = len(grid)
			n = len(grid[0])
			path = [[0, 1], [1, 0], [0, -1], [-1, 0]]
			temp = []
			grid[i][j] = 2
			temp.append([i, j])
			neigh = [[i, j]]
			while len(neigh) > 0:
				r = neigh[0][0]
				c = neigh[0][1]
				neigh.pop(0)
				for a in path:
					nRow = r + a[0]
					nCol = c + a[1]
					if 0 <= nRow < m and 0 <= nCol < n and (grid[nRow][nCol] == 1):
						grid[nRow][nCol] = 2
						temp.append([nRow, nCol])
						neigh.append([nRow, nCol])
			a = temp[0].copy()
			for x in temp:
				x[0] -= a[0]
				x[1] -= a[1]
			if temp not in res:
				res.append(temp.copy())
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					traverse(i, j, grid, res)
		return len(res)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, vis, grid, n, m, sr, sc, drow, dcol, start, island):
		vis[sr][sc] = 1
		island.append((sr - start[0], sc - start[1]))
		for i in range(4):
			nrow = sr + drow[i]
			ncol = sc + dcol[i]
			if 0 <= nrow < n and 0 <= ncol < m and (not vis[nrow][ncol]) and grid[nrow][ncol]:
				self.dfs(vis, grid, n, m, nrow, ncol, drow, dcol, start, island)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		vis = [[0] * m for i in range(n)]
		s = []
		for i in range(n):
			for j in range(m):
				if grid[i][j] and (not vis[i][j]):
					island = []
					start = (i, j)
					self.dfs(vis, grid, n, m, i, j, drow, dcol, start, island)
					if island not in s:
						s.append(island)
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isSafe(self, n, m, x, y):
		return x >= 0 and x < n and (y >= 0) and (y < m)

	def dfs(self, grid, n, m, i, j, visited, l):
		d_x = [-1, 0, 0, 1]
		d_y = [0, -1, 1, 0]
		for u in range(4):
			x = i + d_x[u]
			y = j + d_y[u]
			if self.isSafe(n, m, x, y) and (not visited[x][y]) and (grid[x][y] == 1):
				visited[x][y] = 1
				l.append((x, y))
				self.dfs(grid, n, m, x, y, visited, l)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for j in range(m)] for i in range(n)]
		islands = []
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not visited[i][j]):
					l = []
					visited[i][j] = 1
					l.append((i, j))
					self.dfs(grid, n, m, i, j, visited, l)
					islands.append(l)
		s = set()
		for i in islands:
			(x, y) = i[0]
			temp = []
			for j in i:
				(k, l) = j
				temp.append((k - x, l - y))
			s.add(tuple(temp))
		return len(list(s))


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, i, j, visited, grid, temp_list, org_i, org_j):
		visited[i][j] = 1
		temp_list.append((org_i - i, org_j - j))
		drow = [0, +1, 0, -1]
		dcol = [+1, 0, -1, 0]
		for k in range(0, 4):
			nrow = drow[k] + i
			ncol = dcol[k] + j
			if nrow >= 0 and nrow < len(grid) and (ncol >= 0) and (ncol < len(grid[0])) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
				self.dfs(nrow, ncol, visited, grid, temp_list, org_i, org_j)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		rows = len(grid)
		cols = len(grid[0])
		visited = [[0 for i in range(cols)] for j in range(rows)]
		final_set = set()
		for i in range(rows):
			for j in range(cols):
				if visited[i][j] == 0 and grid[i][j] == 1:
					temp_list = []
					self.dfs(i, j, visited, grid, temp_list, i, j)
					temp_l = tuple(temp_list)
					final_set.add(temp_l)
		return len(final_set)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = [[False] * len(grid[0]) for _ in range(len(grid))]
		s = set()

		def is_valid(i, j):
			if i < 0 or j < 0 or i > len(grid) - 1 or (j > len(grid[0]) - 1) or visited[i][j] or (grid[i][j] == 0):
				return False
			return True
		X = [1, 0, -1, 0]
		Y = [0, 1, 0, -1]

		def bfs(i, j, shape=[]):
			shape = []
			(p_i, p_j) = (i, j)
			q = [[i, j]]
			visited[i][j] = True
			while q:
				(i, j) = q.pop(0)
				shape.append((i - p_i, j - p_j))
				for k in range(4):
					if is_valid(i + X[k], j + Y[k]):
						q.append([i + X[k], j + Y[k]])
						visited[i + X[k]][j + Y[k]] = True
			return shape
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if visited[i][j] == False and grid[i][j] == 1:
					shape = tuple(bfs(i, j))
					s.add(shape)
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, r, c, grid, vis, ans, baser, basec):
		n = len(grid)
		m = len(grid[0])
		xx = [-1, 0, +1, 0]
		yy = [0, +1, 0, -1]
		vis[r][c] = 1
		ans.append((r - baser, c - basec))
		for i in range(4):
			nr = r + xx[i]
			nc = c + yy[i]
			if nr >= 0 and nr < n and (nc >= 0) and (nc < m) and (grid[nr][nc] == 1) and (not vis[nr][nc]):
				self.dfs(nr, nc, grid, vis, ans, baser, basec)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for i in range(n)]
		s = set()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and (not vis[i][j]):
					val = []
					self.dfs(i, j, grid, vis, val, i, j)
					s.add(tuple(val))
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

def dfs(r, c, visit, grid, temp, br, bc):
	(n, m) = (len(grid), len(grid[0]))
	visit[r][c] = 1
	temp.append((r - br, c - bc))
	l = [[-1, 0], [1, 0], [0, -1], [0, 1]]
	for (i, j) in l:
		(nr, nc) = (r + i, c + j)
		if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (grid[nr][nc] == 1) and (not visit[nr][nc]):
			dfs(nr, nc, visit, grid, temp, br, bc)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		visit = [[0] * m for _ in range(n)]
		s = set()
		for i in range(n):
			for j in range(m):
				temp = []
				if not visit[i][j] and grid[i][j] == 1:
					dfs(i, j, visit, grid, temp, i, j)
					s.add(tuple(temp))
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(ROW, COL) = (len(grid), len(grid[0]))
		res = []
		vec = set()

		def dfs(row, col, sr, sc, visited):
			if row < 0 or col < 0 or row == ROW or (col == COL) or (grid[row][col] == 0) or ((row, col) in vec):
				return
			vec.add((row, col))
			visited.add((row - sr, col - sc))
			dfs(row + 1, col, sr, sc, visited) or dfs(row - 1, col, sr, sc, visited) or dfs(row, col + 1, sr, sc, visited) or dfs(row, col - 1, sr, sc, visited)
		for i in range(ROW):
			for j in range(COL):
				visited = set()
				if grid[i][j] == 1 and (i, j) not in vec:
					dfs(i, j, i, j, visited)
					if visited not in res:
						res.append(visited)
		return len(res)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		visited = set()

		def dfs(r, c, base, res):
			visited.add((r, c))
			res.append((base[0] - r, base[1] - c))
			for (dr, dc) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
				if (r + dr, c + dc) not in visited and r + dr in range(m) and (c + dc in range(n)) and (grid[r + dr][c + dc] == 1):
					dfs(r + dr, c + dc, base, res)
		ans = []
		for i in range(len(grid)):
			for j in range(n):
				if grid[i][j] == 1 and (i, j) not in visited:
					res = []
					dfs(i, j, (i, j), res)
					if res not in ans:
						ans.append(res)
		return len(ans)


from collections import deque
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def check(self, row, col, x, y):
		if 0 <= x < row and 0 <= y < col:
			return True
		return False

	def exp(self, grid, node, visited):
		(row, col) = (len(grid), len(grid[0]))
		(dir_x, dir_y) = ([0, 0, 1, -1], [1, -1, 0, 0])
		q = deque([])
		q.append(tuple(node))
		cord = []
		while len(q) != 0:
			a = q.pop()
			cord.append([a[0], a[1]])
			visited.add(a)
			for i in range(4):
				(new_x, new_y) = (a[0] + dir_x[i], a[1] + dir_y[i])
				if self.check(row, col, new_x, new_y):
					elm = tuple([new_x, new_y])
					if elm not in visited and grid[new_x][new_y] == 1:
						q.append(elm)
		return cord

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = set()
		res = []
		data = set()
		(row, col) = (len(grid), len(grid[0]))
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 1 and tuple([i, j]) not in visited:
					a = self.exp(grid, [i, j], visited)
					if a[0] != [0, 0]:
						base = [a[0][0], a[0][1]]
						for k in range(len(a)):
							a[k][0] -= base[0]
							a[k][1] -= base[1]
					if a not in res:
						res.append(a)
		return len(res)


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def countDistinctIslands(self, grid) -> int:

		def dfs(i, j, si, sj):
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and (grid[i][j] == 1):
				grid[i][j] *= -1
				isl.append((i - si, j - sj))
				dirs = [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]
				for (ii, jj) in dirs:
					dfs(ii, jj, si, sj)
		isls = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] != 1:
					continue
				isl = []
				dfs(i, j, i, j)
				isls.add(tuple(isl))
		return len(isls)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		res = set()
		visited = [[False for i in range(n)] for j in range(m)]
		for i in range(m):
			for j in range(n):
				temp = []
				if grid[i][j] == 1 and visited[i][j] == False:
					self.dfs(i, j, visited, grid, temp, m, n, i, j)
					res.add(tuple(temp))
		return len(res)

	def dfs(self, i, j, visited, grid, temp, m, n, row, col):
		visited[i][j] = True
		temp.append((row - i, col - j))
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		for k in range(4):
			nrow = i + drow[k]
			ncol = j + dcol[k]
			if nrow >= 0 and nrow < m and (ncol >= 0) and (ncol < n) and (visited[nrow][ncol] == False) and (grid[nrow][ncol] == 1):
				self.dfs(nrow, ncol, visited, grid, temp, m, n, row, col)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = []
		arr = []
		st = []
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			visited.append([])
			for j in range(n):
				visited[i].append(0)

		def dfs(i, j, visited, grid, arr, row0, col0):
			visited[i][j] = 1
			arr.append([i - row0, j - col0])
			rows = [-1, 0, 1, 0]
			cols = [0, 1, -0, -1]
			for k in range(4):
				nrow = rows[k] + i
				ncol = cols[k] + j
				if nrow >= 0 and ncol >= 0 and (nrow < m) and (ncol < n) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					dfs(nrow, ncol, visited, grid, arr, row0, col0)
		for i in range(m):
			for j in range(n):
				if visited[i][j] == 0 and grid[i][j] == 1:
					dfs(i, j, visited, grid, arr, i, j)
					if arr in st:
						pass
					else:
						st.append(arr)
					arr = []
		return len(st)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		dr = [-1, 0, 1, 0]
		dc = [0, -1, 0, 1]

		def dfs(r, c, lst, ro, co):
			vis[r][c] = 1
			lst.append((r - ro, c - co))
			for i in range(4):
				row = r + dr[i]
				col = c + dc[i]
				if (row >= 0 and row < n) and (col >= 0 and col < m) and (not vis[row][col]) and (grid[row][col] == 1):
					dfs(row, col, lst, ro, co)
		n = len(grid)
		m = len(grid[0])
		vis = [[0] * m for i in range(n)]
		s = set()
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and grid[i][j] == 1:
					l = []
					dfs(i, j, l, i, j)
					s.add(tuple(l))
		return len(s)


import sys
from collections import deque
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		sign = set()
		n = len(grid)
		m = len(grid[0])
		marked = [[0 for _ in range(m)] for _ in range(n)]
		dx = [-1, 0, 0, 1]
		dy = [0, -1, 1, 0]
		q = deque()
		for i in range(n):
			for j in range(m):
				if marked[i][j] == 0 and grid[i][j] == 1:
					total = []
					num = 0
					q.append(i)
					q.append(j)
					marked[i][j] = 1
					while len(q) > 0:
						x = q.popleft()
						y = q.popleft()
						total.append((x - i, y - j))
						num += 1
						for k in range(4):
							nx = x + dx[k]
							ny = y + dy[k]
							if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (not marked[nx][ny]) and grid[nx][ny]:
								marked[nx][ny] = 1
								q.append(nx)
								q.append(ny)
					s1 = 0
					s2 = 0
					for t in total:
						s1 = s1 * 10 + t[0]
						s2 = s2 * 10 + t[1]
					sign.add((s1, s2))
		return len(sign)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = []
		m = len(grid)
		n = len(grid[0])
		lst1 = []
		for i in range(m):
			visited.append([])
			for j in range(n):
				visited[i].append(0)

		def dfs(row, col, visited, grid, lst):
			lst.append([row, col])
			m = len(grid)
			n = len(grid[0])
			visited[row][col] = 1
			rows = [1, 0, -1, 0]
			cols = [0, 1, 0, -1]
			for i in range(4):
				nrow = rows[i] + row
				ncol = cols[i] + col
				if nrow >= 0 and ncol >= 0 and (nrow < m) and (ncol < n):
					if visited[nrow][ncol] == 0 and grid[nrow][ncol] == 1:
						visited[nrow][ncol] = 1
						dfs(nrow, ncol, visited, grid, lst)
		for i in range(m):
			for j in range(n):
				lst = []
				if grid[i][j] == 1 and visited[i][j] == 0:
					dfs(i, j, visited, grid, lst)
					base_0 = lst[0][0]
					base_1 = lst[0][1]
					for k in range(len(lst)):
						for l in range(len(lst[0])):
							if l == 0:
								lst[k][l] = lst[k][l] - base_0
							elif l == 1:
								lst[k][l] = lst[k][l] - base_1
					lst1.append(lst)
		lst1.sort()
		if len(lst1) == 1:
			return 1
		i = 0
		cnt = 0
		while i < len(lst1) - 1:
			if lst1[i] == lst1[i + 1]:
				lst1.remove(lst1[i])
				i -= 1
			i += 1
		return len(lst1)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, grid, vis, temp, cur_row, cur_col):
		n_row = len(grid)
		n_col = len(grid[0])
		vis[cur_row][cur_col] = True
		temp.append([cur_row, cur_col])
		if cur_col + 1 < n_col and grid[cur_row][cur_col + 1] == 1 and (vis[cur_row][cur_col + 1] == False):
			self.dfs(grid, vis, temp, cur_row, cur_col + 1)
		if cur_row + 1 < n_row and grid[cur_row + 1][cur_col] == 1 and (vis[cur_row + 1][cur_col] == False):
			self.dfs(grid, vis, temp, cur_row + 1, cur_col)
		if cur_row - 1 >= 0 and grid[cur_row - 1][cur_col] == 1 and (vis[cur_row - 1][cur_col] == False):
			self.dfs(grid, vis, temp, cur_row - 1, cur_col)
		if cur_col - 1 >= 0 and grid[cur_row][cur_col - 1] == 1 and (vis[cur_row][cur_col - 1] == False):
			self.dfs(grid, vis, temp, cur_row, cur_col - 1)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		grid_d = {}
		n_row = len(grid)
		n_col = len(grid[0])
		vis = [[False for i in range(n_col)] for j in range(n_row)]
		for i in range(n_row):
			for j in range(n_col):
				if vis[i][j] == False and grid[i][j] == 1:
					temp = []
					self.dfs(grid, vis, temp, i, j)
					base_row = temp[0][0]
					base_col = temp[0][1]
					for tup in temp:
						tup[0] = tup[0] - base_row
						tup[1] = tup[1] - base_col
					io = []
					for tup in temp:
						io.append((tup[0], tup[1]))
					tyu = tuple(io)
					grid_d[tyu] = True
		return len(grid_d)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(i, j, lis, pi, pj):
			vis[i][j] = 1
			lis.append((i - pi, j - pj))
			for nex in dict:
				(ni, nj) = (i + nex[0], j + nex[1])
				if (ni < len(grid) and ni >= 0 and (nj >= 0) and (nj < len(grid[0]))) and (not vis[ni][nj]) and (grid[ni][nj] == 1):
					dfs(ni, nj, lis, pi, pj)
		dict = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		vis = []
		for i in range(len(grid)):
			vis.append([0] * len(grid[0]))
		land = 0
		res = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if not vis[i][j] and grid[i][j] == 1:
					lis = []
					dfs(i, j, lis, i, j)
					res.add(tuple(lis))
		return len(res)


import sys
from typing import List
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def in_range(self, i, j, n, m):
		return i >= 0 and i < n and (j >= 0) and (j < m)

	def find_diff(self, arr):
		if len(arr) == 0:
			return []
		(x, y) = arr[0]
		dup = []
		for i in range(len(arr)):
			dup.append((arr[i][0] - x, arr[i][1] - y))
		return dup

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		is_visited = [[False for j in range(m)] for i in range(n)]
		que = deque()
		neighs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		s = set()
		for i in range(n):
			for j in range(m):
				dist = []
				if not is_visited[i][j] and grid[i][j] == 1:
					que.append((i, j))
					is_visited[i][j] = True
					dist.append((i, j))
				while len(que):
					(oi, oj) = que.popleft()
					for (di, dj) in neighs:
						(ni, nj) = (oi + di, oj + dj)
						if self.in_range(ni, nj, n, m) and (not is_visited[ni][nj]) and (grid[ni][nj] == 1):
							que.append((ni, nj))
							is_visited[ni][nj] = True
							dist.append((ni, nj))
				tup = tuple(self.find_diff(dist))
				if len(tup) != 0:
					s.add(tup)
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(row, col, v, l, br, bc):
			M = len(grid)
			N = len(grid[0])
			t = (row - br, col - bc)
			l.append(t)
			dr = [-1, 0, 1, 0]
			dc = [0, 1, 0, -1]
			for i in range(4):
				nr = dr[i] + row
				nc = dc[i] + col
				if nr > -1 and nr < M and (nc > -1) and (nc < N) and (grid[nr][nc] == 1) and (v[nr][nc] == 0):
					v[nr][nc] = 1
					dfs(nr, nc, v, l, br, bc)
		s = set()
		M = len(grid)
		N = len(grid[0])
		v = [[0] * N for i in range(M)]
		for i in range(M):
			for j in range(N):
				if grid[i][j] == 1 and v[i][j] == 0:
					l = []
					v[i][j] = 1
					dfs(i, j, v, l, i, j)
					s.add(tuple(l))
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(row, col, v, vec, grid, row0, col0):
			n = len(grid)
			m = len(grid[0])
			v[row][col] = 1
			vec.append((row - row0, col - col0))
			dr = [-1, 0, 1, 0]
			dc = [0, -1, 0, 1]
			for i in range(4):
				nrow = row + dr[i]
				ncol = col + dc[i]
				if 0 <= nrow < n and 0 <= ncol < m and (not v[nrow][ncol]) and (grid[nrow][ncol] == 1):
					dfs(nrow, ncol, v, vec, grid, row0, col0)
		n = len(grid)
		m = len(grid[0])
		v = [[0] * m for _ in range(n)]
		s = set()
		for i in range(n):
			for j in range(m):
				if not v[i][j] and grid[i][j] == 1:
					vec = []
					dfs(i, j, v, vec, grid, i, j)
					s.add(tuple(vec))
		return len(s)


def dfs(i, j, row, col, m, n, visited, temp, grid):
	if i < 0 or i >= m or j < 0 or (j >= n) or (visited[i][j] == True) or (grid[i][j] == 0):
		return
	temp.add((row - i, col - j))
	visited[i][j] = True
	dfs(i, j + 1, row, col, m, n, visited, temp, grid)
	dfs(i + 1, j, row, col, m, n, visited, temp, grid)
	dfs(i - 1, j, row, col, m, n, visited, temp, grid)
	dfs(i, j - 1, row, col, m, n, visited, temp, grid)
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		res = []
		temp = set()
		d = {}
		m = len(grid)
		n = len(grid[0])
		visited = [[False for j in range(n)] for i in range(m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1 and visited[i][j] == False:
					temp = set()
					dfs(i, j, i, j, m, n, visited, temp, grid)
					if temp not in res:
						res.append(temp)
		return len(res)


import sys
from typing import List
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isValid(self, row, col, grid, vis):
		(n, m) = (len(grid), len(grid[0]))
		if row < n and row >= 0 and (col < m) and (col >= 0) and (grid[row][col] == 1) and (vis[row][col] == 0):
			return True
		else:
			return False

	def dfs(self, i, j, grid, vis, lt, R, C):
		if not self.isValid(i, j, grid, vis):
			return
		vis[i][j] = 1
		lt.append((R - i, C - j))
		directions = [[i + 1, j], [i, j + 1], [i - 1, j], [i, j - 1]]
		for (r, c) in directions:
			self.dfs(r, c, grid, vis, lt, R, C)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		vis = [[0 for j in range(m)] for i in range(n)]
		island = set()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					lt = []
					self.dfs(i, j, grid, vis, lt, i, j)
					lt = tuple(lt)
					island.add(lt)
		return len(island)


import sys
from typing import List
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def isValid(self, row, col, grid, vis):
		(n, m) = (len(grid), len(grid[0]))
		if row < n and row >= 0 and (col < m) and (col >= 0) and (grid[row][col] == 1) and (vis[row][col] == 0):
			return True
		else:
			return False

	def bfs(self, i, j, grid, vis, lt):
		vis[i][j] = 1
		base = [i, j]
		queue = deque()
		queue.append([i, j])
		while queue:
			(r, c) = queue.popleft()
			lt.append((r - base[0], c - base[1]))
			directions = [[r + 1, c], [r, c + 1], [r - 1, c], [r, c - 1]]
			for (row, col) in directions:
				if self.isValid(row, col, grid, vis):
					queue.append([row, col])
					vis[row][col] = 1

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		vis = [[0 for j in range(m)] for i in range(n)]
		island = set()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					lt = []
					self.bfs(i, j, grid, vis, lt)
					lt = tuple(lt)
					island.add(lt)
		return len(island)


import collections
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		vis = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
		ans = set()

		def bfs(i, j, grid, vis, points, x, y):
			deque = collections.deque()
			deque.append((i, j))
			while len(deque) > 0:
				for i in range(len(deque)):
					dt = deque.popleft()
					(row, col) = (dt[0], dt[1])
					dltRow = [-1, 0, 1, 0]
					dltCol = [0, 1, 0, -1]
					for k in range(len(dltCol)):
						newRow = row + dltRow[k]
						newCol = col + dltCol[k]
						if newRow >= 0 and newRow < len(grid) and (newCol >= 0) and (newCol < len(grid[0])) and (vis[newRow][newCol] == 0) and (grid[newRow][newCol] == 1):
							vis[newRow][newCol] = 1
							deque.append((newRow, newCol))
							points.append(newRow - x)
							points.append(newCol - y)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if vis[i][j] == 0 and grid[i][j] == 1:
					vis[i][j] = 1
					points = []
					points.append(i - i)
					points.append(j - j)
					bfs(i, j, grid, vis, points, i, j)
					newStr = ''.join([str(eachInt) for eachInt in points])
					ans.add(newStr)
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, row, col, visited, grid, base, land):
		land.append((0, 0))
		n = len(grid)
		m = len(grid[0])
		visited[row][col] = 1
		delrow = (-1, 0, 1, 0)
		delcol = (0, 1, 0, -1)
		for i in range(4):
			nrow = row + delrow[i]
			ncol = col + delcol[i]
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
				x = nrow - base[0]
				y = ncol - base[1]
				land.append((x, y))
				self.dfs(nrow, ncol, visited, grid, base, land)
		return land

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		visited = [[0 for i in range(m)] for i in range(n)]
		st = set()
		for i in range(n):
			for j in range(m):
				land = []
				if visited[i][j] == 0 and grid[i][j] == 1:
					base = (i, j)
					st.add(tuple(self.dfs(i, j, visited, grid, base, land)))
		return len(st)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, row, col, n, m, grid, vis, ans):
		que = []
		que.append((row, col))
		arr = []
		arr.append((row - row, col - col))
		vis[row][col] = 1
		dx = [0, -1, 0, 1]
		dy = [-1, 0, 1, 0]
		while len(que):
			(x, y) = que.pop(-1)
			for i in range(4):
				nrow = x + dx[i]
				ncol = y + dy[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] != 1) and (grid[nrow][ncol] == 1):
					que.append((nrow, ncol))
					vis[nrow][ncol] = 1
					arr.append((nrow - row, ncol - col))
		if len(arr):
			ans.add(tuple(arr))
		return

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		vis = [[0 for x in range(m)] for x in range(n)]
		ans = set()
		for i in range(n):
			for j in range(m):
				if vis[i][j] != 1 and grid[i][j] == 1:
					self.dfs(i, j, n, m, grid, vis, ans)
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, grid, start, end, i, j, n, m, ls):
		if i < 0 or i >= n or j < 0 or (j >= m) or (grid[i][j] == 0):
			return
		grid[i][j] = 0
		ls.append([i - start, j - end])
		self.dfs(grid, start, end, i + 1, j, n, m, ls)
		self.dfs(grid, start, end, i - 1, j, n, m, ls)
		self.dfs(grid, start, end, i, j - 1, n, m, ls)
		self.dfs(grid, start, end, i, j + 1, n, m, ls)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		x = set()
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					ls = []
					self.dfs(grid, i, j, i, j, n, m, ls)
					x.add(tuple(map(tuple, ls)))
		return len(x)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = [[0] * len(grid[0]) for _ in range(len(grid))]

		def dfs(row: int, col: int, temp: list, row_base: int, col_base: int):
			visited[row][col] = 1
			temp.append((row - row_base, col - col_base))
			(r, c) = (row, col)
			check = [[r - 1, c], [r + 1, c], [r, c + 1], [r, c - 1]]
			for (temp_r, temp_c) in check:
				if 0 <= temp_r < len(grid) and 0 <= temp_c < len(grid[0]) and (grid[temp_r][temp_c] == 1) and (visited[temp_r][temp_c] == 0):
					dfs(temp_r, temp_c, temp, row_base, col_base)
		islands = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and visited[i][j] == 0:
					temp = []
					dfs(i, j, temp, i, j)
					islands.add(tuple(temp))
		return len(islands)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		visited = [[0 for i in range(n)] for j in range(m)]
		count = 0
		directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		vectorSet = set()

		def dfs(x, y, baseX, baseY):
			nonlocal visited, vector, vectorSet, directions
			visited[x][y] = 1
			vector.append((baseX - x, baseY - y))
			for (i, j) in directions:
				r = x + i
				c = y + j
				if -1 < r < m and -1 < c < n and (grid[r][c] == 1) and (not visited[r][c]):
					dfs(r, c, baseX, baseY)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1 and (not visited[i][j]):
					vector = []
					dfs(i, j, i, j)
					vectorSet.add(tuple(vector))
		return len(vectorSet)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		visited = set()
		islands = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if (i, j) not in visited and grid[i][j] == 1:
					shape = []
					self.floodfill(i, j, shape, (i, j), grid, visited)
					islands.add(tuple(sorted(shape)))
		return len(islands)

	def floodfill(self, r, c, shape, start, grid, visited):
		for (dx, dy) in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
			(row, col) = (r + dx, c + dy)
			if 0 <= row < len(grid) and 0 <= col < len(grid[0]) and ((row, col) not in visited) and (grid[row][col] == 1):
				visited.add((row, col))
				shape.append((row - start[0], col - start[1]))
				self.floodfill(row, col, shape, start, grid, visited)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(i, j, temp, basei, basej):
			vis.add((i, j))
			temp.append((basei - i, basej - j))
			drow = [-1, 0, 1, 0]
			dcol = [0, 1, 0, -1]
			m = len(grid)
			n = len(grid[0])
			for d in range(4):
				(row, col) = (i + drow[d], j + dcol[d])
				if row >= 0 and row < m and (col < n) and (col >= 0):
					if grid[row][col] == 1 and (row, col) not in vis:
						dfs(row, col, temp, basei, basej)
		vis = set()
		m = len(grid)
		n = len(grid[0])
		count = 0
		distinct = set()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1 and (i, j) not in vis:
					temp = []
					dfs(i, j, temp, i, j)
					distinct.add(tuple(temp))
					count += 1
		return len(distinct)


import sys
from typing import List
from collections import deque
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		visited = [[0] * m for _ in range(n)]
		dis = set()

		def isValid(i, j, grid):
			return True if 0 <= i < n and 0 <= j < m and (grid[i][j] == 1) and (visited[i][j] == 0) else False

		def dfs(i, j, grid, visited, pi, pj, temp):
			visited[i][j] = 1
			temp.append(tuple([i - pi, j - pj]))
			for (a, b) in ([i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]):
				if isValid(a, b, grid):
					dfs(a, b, grid, visited, pi, pj, temp)
		for i in range(n):
			for j in range(m):
				if visited[i][j] == 0 and grid[i][j] == 1:
					t = list()
					dfs(i, j, grid, visited, i, j, t)
					dis.add(tuple(t))
		return len(dis)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		rows = len(grid)
		cols = len(grid[0])
		islands = set()

		def isOutOfBounday(row, col):
			return row < 0 or row >= rows or col < 0 or (col >= cols)

		def bfs(row, col, temp, baser, basec):
			if isOutOfBounday(row, col) or grid[row][col] == 0:
				return
			temp.append((row - baser, col - basec))
			grid[row][col] = 0
			for (xx, yy) in [[-1 + row, col], [1 + row, col], [row, -1 + col], [row, 1 + col]]:
				bfs(xx, yy, temp, baser, basec)
		for i in range(rows):
			for j in range(cols):
				temp = []
				bfs(i, j, temp, i, j)
				if temp:
					islands.add(tuple(temp))
		return len(islands)


def dfs(grid, vis, ans, r, c, temp, r0, c0):
	vis[r][c] = 1
	temp.append((r - r0, c - c0))
	dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]
	for i in range(4):
		nr = dx[i] + r
		nc = dy[i] + c
		if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (grid[nr][nc] == 1) and (vis[nr][nc] == 0):
			dfs(grid, vis, ans, nr, nc, temp, r0, c0)
import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		ans = set()
		vis = [[0 for i in range(len(grid[0]))] for i in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1 and vis[i][j] == 0:
					temp = []
					dfs(grid, vis, ans, i, j, temp, i, j)
					ans.add(tuple(temp))
		return len(ans)


import sys
from typing import *
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for i in range(m)] for j in range(n)]

		def dfs(baseR, baseC, grid, vis, t: List, r, c):
			vis[r][c] = 1
			t.append((r - baseR, c - baseC))
			delrow = [-1, 0, 1, 0]
			delcol = [0, -1, 0, 1]
			for i in range(4):
				nrow = r + delrow[i]
				ncol = c + delcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (vis[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					dfs(baseR, baseC, grid, vis, t, nrow, ncol)
		s = set()
		for i in range(n):
			for j in range(m):
				if vis[i][j] == 0 and grid[i][j] == 1:
					t = []
					dfs(i, j, grid, vis, t, i, j)
					s.add(tuple(t))
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(i, j, srcrow, srccol, store):
			m = len(grid)
			n = len(grid[0])
			vis.add((i, j))
			store.append((i - srcrow, j - srccol))
			drow = [-1, 0, 1, 0]
			dcol = [0, 1, 0, -1]
			for d in range(4):
				(row, col) = (drow[d] + i, dcol[d] + j)
				if row >= 0 and row < m and (col >= 0) and (col < n):
					if grid[row][col] == 1 and (row, col) not in vis:
						vis.add((row, col))
						dfs(row, col, srcrow, srccol, store)
		vis = set()
		res = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if (i, j) not in vis and grid[i][j] == 1:
					store = []
					dfs(i, j, i, j, store)
					res.append(store)
		ans = set()
		for lst in res:
			ans.add(tuple(lst))
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)
from collections import *

class Solution:

	def valid(self, i, j, grid, visited):
		if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (visited[i][j] == 1) or (grid[i][j] == 0):
			return False
		return True

	def f(self, i, j, s, e, grid, visited, ans):
		visited[i][j] = 1
		ans.append(tuple([i - s, j - e]))
		for k in range(4):
			if self.valid(i + self.dx[k], j + self.dy[k], grid, visited):
				self.f(i + self.dx[k], j + self.dy[k], s, e, grid, visited, ans)

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		self.dx = [1, -1, 0, 0]
		self.dy = [0, 0, 1, -1]
		d = defaultdict(int)
		visited = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				ans = []
				if visited[i][j] == 0 and grid[i][j] == 1:
					self.f(i, j, i, j, grid, visited, ans)
				if ans != []:
					d[tuple(ans)] = 1
		return len(d)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

def dfs(row, col, grid, vis, a, prerow, precol):
	n = len(grid)
	m = len(grid[0])
	vis[row][col] = True
	a.append((row - prerow, col - precol))
	d = [[-1, 0], [0, 1], [1, 0], [0, -1]]
	for i in d:
		delrow = row + i[0]
		delcol = col + i[1]
		if 0 <= delrow < n and 0 <= delcol < m and (not vis[delrow][delcol]) and (grid[delrow][delcol] == 1):
			dfs(delrow, delcol, grid, vis, a, prerow, precol)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[False] * m for i in range(n)]
		b = set()
		for i in range(n):
			for j in range(m):
				a = []
				if grid[i][j] == 1 and (not vis[i][j]):
					dfs(i, j, grid, vis, a, i, j)
					t = tuple(a)
					b.add(t)
		return len(b)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(r, c, pr, pc, curset):
			visited.add((r, c))
			curset.append((r - pr, c - pc))
			for (rr, cc) in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
				nr = rr + r
				nc = cc + c
				if nr in range(n) and nc in range(m) and ((nr, nc) not in visited) and (grid[nr][nc] == 1):
					dfs(nr, nc, pr, pc, curset)
		n = len(grid)
		m = len(grid[0])
		visited = set()
		shapes = set()
		for i in range(n):
			for j in range(m):
				if (i, j) not in visited and grid[i][j] == 1:
					curset = []
					dfs(i, j, i, j, curset)
					t = tuple(curset)
					shapes.add(t)
		return len(shapes)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		self.dir = [[-1, 0], [0, -1], [0, 1], [1, 0]]

		def bfs(row, col, grid, pattern, src_r, src_c):
			if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[0])) or (grid[row][col] != 1):
				return
			grid[row][col] = 2
			pattern.append(str(src_r - row) + str(src_c - col))
			for i in self.dir:
				(new_r, new_c) = (row + i[0], col + i[1])
				bfs(new_r, new_c, grid, pattern, src_r, src_c)
		S = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				pattern = []
				if grid[i][j] == 1:
					bfs(i, j, grid, pattern, i, j)
					S.add(tuple(pattern))
		return len(S)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])

		def DFS(i, j, base1, base2, pat):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] != 1):
				return
			grid[i][j] = 2
			pat.append(str(base1 - i) + str(base2 - j))
			DFS(i + 1, j, base1, base2, pat)
			DFS(i - 1, j, base1, base2, pat)
			DFS(i, j - 1, base1, base2, pat)
			DFS(i, j + 1, base1, base2, pat)
		ans = set()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					pat = []
					DFS(i, j, i, j, pat)
					ans.add(tuple(pat))
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(grid, srci, srcj, i, j, pattern):
			if i < 0 or i >= n or j < 0 or (j >= m) or (grid[i][j] != 1):
				return
			grid[i][j] = 2
			pattern.append(str(srci - i) + str(srcj - j))
			for k in directions:
				new_row = i + k[0]
				new_col = j + k[1]
				dfs(grid, srci, srcj, new_row, new_col, pattern)
		hash_map = set()
		n = len(grid)
		m = len(grid[0])
		directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					pattern = list()
					dfs(grid, i, j, i, j, pattern)
					hash_map.add(tuple(pattern))
		return len(hash_map)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(row, col, grid, sr, sc, pattern):
			directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]
			if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[0])) or (grid[row][col] != 1):
				return
			grid[row][col] = 2
			pattern.append((sr - row, sc - col))
			for direction in directions:
				nrow = row + direction[0]
				ncol = col + direction[1]
				dfs(nrow, ncol, grid, sr, sc, pattern)
		hashset = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					pattern = []
					dfs(i, j, grid, i, j, pattern)
					hashset.add(tuple(pattern))
		return len(hashset)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]

		def dfs(row, col, grid, src_row, src_col, pattern):
			if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[0])) or (grid[row][col] != 1):
				return
			grid[row][col] = 2
			pattern.append((src_row - row, src_col - col))
			for direction in directions:
				new_row = row + direction[0]
				new_col = col + direction[1]
				dfs(new_row, new_col, grid, src_row, src_col, pattern)
		s = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					pattern = []
					dfs(i, j, grid, i, j, pattern)
					s.add(tuple(pattern))
		return len(s)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:

		def dfs(r, c, src1, src2, pattern):
			if r < 0 or r >= m or c < 0 or (c >= n) or (grid[r][c] != 1):
				return
			grid[r][c] = 2
			pattern.append(str(src1 - r) + str(src2 - c))
			for (x, y) in direct:
				dfs(r + x, c + y, src1, src2, pattern)
		ans = set()
		m = len(grid)
		n = len(grid[0])
		direct = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					pattern = []
					dfs(i, j, i, j, pattern)
					ans.add(tuple(pattern))
		return len(ans)


import sys
from typing import List
sys.setrecursionlimit(10 ** 8)

class Solution:

	def countDistinctIslands(self, grid: List[List[int]]) -> int:
		directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]

		def dfs(row, col, grid, srcRow, srcCol, pattern):
			if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[0])) or (grid[row][col] != 1):
				return
			grid[row][col] = 2
			pattern.append((srcRow - row, srcCol - col))
			for dir in directions:
				newRow = row + dir[0]
				newCol = col + dir[1]
				dfs(newRow, newCol, grid, srcRow, srcCol, pattern)
		s = set()
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					pattern = []
					dfs(i, j, grid, i, j, pattern)
					s.add(tuple(pattern))
		return len(s)