694. Number of Distinct Islands

https://leetcode.com/problems/number-of-distinct-islands/leetcode.com

找岛题，基础模版应该就是Q200，BFS/DFS即可，这题的要求是distinct，可以想到维护一个hashset去存储岛的形状，那么问题就变成如何定义「岛的形状」？即设计一种hash，让相同形状的岛即便坐标不同也会得到一样的hash结果。

200. Number of Islands

简单方法就是找到岛的时候，按照第一个点的坐标是 (0,0) 来存储岛屿，加上我们是有序扫描（从左到右，从上往下），两个形状相同岛屿存储的坐标信息一定是相同的。

P.S. test run 发现 list 不能被hash，需要改成tuple

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])
        
        # 用bfs找到起始点为(y_s,x_s)的岛屿的形状
        def bfs(y_s, x_s):
            q = collections.deque([(y_s, x_s)])
            shape = []
            while q:
                y, x = q.popleft()
                # 要确认每个点的相对坐标，就拿它实际坐标减去起始点坐标(y_s,x_s)
                shape.append((y-y_s, x-x_s))
                for y_n, x_n in [(y+1, x), (y-1, x), (y, x+1), (y, x-1)]:
                    if 0<=y_n<m and 0<=x_n<n and (y_n,x_n) not in self.visited and grid[y_n][x_n] == 1: q.append((y_n, x_n))
                    self.visited.add((y_n, x_n))
            return shape

        self.visited, shapes = set(), set()
        for i in range(m):
            for j in range(n):
                if (i, j) not in self.visited and grid[i][j] == 1:
                    self.visited.add((i,j))
                    # list不能被hash，需要改成tuple
                    shapes.add(tuple(bfs(i, j)))
        
        return len(shapes)