TikTok 同形岛屿：平移去重，再把旋转与翻转归为一类

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 按四邻接提取陆地分量，基线只允许平移；追问允许平移、90°倍数旋转及镜像。
• 比较离散格子形状，不允许任意角度旋转、伸缩或裁剪；面积相等并不代表同形。
• 返回不同形状种类数，若要返回每类岛屿列表应保留岛屿ID。

解题路线

1. 先用BFS收集岛屿所有(x,y)，不把发现顺序作为签名。不同起点/邻居顺序会改变遍历序列，却不改变形状，排序坐标可消除这个无关差异。
2. 只允许平移时，分别减去min x/min y再排序成tuple。相差固定向量的形状会产生同一归一化集合；反过来同签名意味着原坐标只差一个平移。
3. 允许旋转/镜像时枚举(x,y)、(x,−y)、(−x,y)、(−x,−y)、(y,x)、(y,−x)、(−y,x)、(−y,−x)。这些正好覆盖正方格子的八种方向对称，不需要猜旋转次数。
4. 每个变换都重新减min x/min y并排序，取字典序最小签名。这是canonical代表：同一对称轨道的所有岛屿拥有同样候选集合，因此最小值相同。
5. 不允许镜像时只选四种旋转，不能用八种变换误合并手性形状。分量提取的邻接合同也要保持一致，否则先提取错误分量再canonical也无法挽救。
6. 按边方向DFS编码也可判平移形状，但必须记录回退/空分支，否则不同拓扑可能碰撞。坐标签名占空间较多但更容易证明，等大岛屿也能明显区分。
7. 相同面积、周长或距离多重集都不是通用形状等价判据。独立验证用复数旋转/共轭和配对平移判断，而非再写一遍八变换最小签名，检验结果种类数。

手动走一遍

两格横条与两格竖条：仅平移时是两类，允许旋转时是一类。L形的左右镜像只在允许反射时归同类。一个四格直条与一个2×2方块面积相同，但任何允许变换都不能把它们互换。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""0/1 rectangular grid, four neighbors, BFS without mutating input.
Shape equivalence: translation alone or translation + rotations/reflections.
"""
from collections import deque


def island_cells(grid):
    if not grid:
        return []
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols or any(v not in (0, 1) for v in row) for row in grid):
        raise ValueError('rectangular binary grid required')
    seen, components = set(), []
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or (r, c) in seen:
                continue
            seen.add((r, c))
            queue = deque([(r, c)])
            cells = []
            while queue:
                x, y = queue.popleft()
                cells.append((x, y))
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    a, b = x + dx, y + dy
                    if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1 and (a, b) not in seen:
                        seen.add((a, b))
                        queue.append((a, b))
            components.append(cells)
    return components


def normalize(cells):
    x0 = min(x for x, y in cells)
    y0 = min(y for x, y in cells)
    return tuple(sorted((x - x0, y - y0) for x, y in cells))


def distinct_island_shapes(grid, rotations_reflections=False):
    signatures = set()
    for cells in island_cells(grid):
        if not rotations_reflections:
            signatures.add(normalize(cells))
        else:
            variants = [[] for _ in range(8)]
            for x, y in cells:
                for target, point in zip(variants, ((x, y), (x, -y), (-x, y), (-x, -y),
                                                   (y, x), (y, -x), (-y, x), (-y, -x))):
                    target.append(point)
            signatures.add(min(normalize(v) for v in variants))
    return len(signatures)


def count_islands(grid):
    return len(island_cells(grid))


def largest_island_area(grid):
    return max((len(cells) for cells in island_cells(grid)), default=0)

复杂度

提取分量O(RC)。每个大小s岛排序O(s log s)，八种变换是常数倍，总O(RC+Σs log s)，最坏O(RC log(RC))；所有坐标和签名O(RC)空间。

易错点与追问

容易失分的边界

• 面积相等就判同形。
• 直接哈希BFS顺序。
• 变换后不重新归一化。
• 只旋转合同却也加入镜像。

继续深挖

• 若只允许旋转，候选有哪些？
• 怎样返回每类出现频次？
• 形状签名如何序列化避免歧义？
• 输入岛屿极大怎样降低排序成本？