【LeetCode 深度优先搜索专项】不同岛屿的数量 II（711）

文章目录

• 1. 题目
• • 1.1 示例
  • 1.2 说明
  • 1.3 提示
  • 1.4 进阶
• 2. 解法一（深度优先搜索）
• • 2.1 分析
  • 2.2 解答
  • 2.3 复杂度

1. 题目

给定一个 $m\times n$ 的二维矩阵 grid ，使用或上、或下、或左、或右方向上相接的一组 $1$ 代表一个岛屿。可以假定矩阵以外的区域都是海水。

如果两个岛屿之间形状相同，或者旋转（旋转角度仅可以为 $90$ 、 $180$ 或 $270$ 度）之后形状相同，或者镜像（可以沿上下或左右镜像）之后形状相同，就称这两个岛屿是相同的。

要求返回给定 grid 中包含的不同岛屿数量。

1.1 示例

• 示例 $1$：

  • 输入： grid = [[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 1, 1]]
  • 输出： $1$
  • 解释：如下图所示，将左上角的岛屿顺时针旋转 $180$ 度之后将得到和右下角完全相同的岛屿。

• 示例 $2$ ：

  • 输入： grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]]
  • 输出： $1$

1.2 说明

• 来源：力扣（LeetCode）
• 链接：https://leetcode-cn.com/problems/number-of-distinct-islands-ii

1.3 提示

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 仅可为 $0$ 或者 $1$

1.4 进阶

你可以使用多种方法求解该问题么？

2. 解法一（深度优先搜索）

2.1 分析

作者：LeetCode

这道题是【LeetCode 深度优先搜索专项】不同岛屿的数量（694）的加强版，不同的是这道题规定两个岛屿仅通过平移，旋转和翻转能够重合，它们的形状就相同。

解决本题的大致思路为：首先找出每个岛屿，随后将它进行旋转和翻转操作得到各种不同的情况，接着对这些情况分别进行归一化处理，然后对归一化结果进行哈希得到具有唯一性的签名，最终所有岛屿经所有变换并归一化且哈希后得到的不同签名数量就是满足要求的不同岛屿数量。

作者： jason-2

首先，为了模拟岛屿的旋转和翻转变换，可以先将岛屿的每块陆地坐标 $(x,y)$ 都看作向量，然后利用解析几何的知识先计算出每个向量变换后的结果，最终所有通过相同变换后的向量就自然地组成了对应岛屿经相应变换后得到的结果。具体地：

• 由于向量 $(x,y)$ 和其旋转 $90$ 度和 $270$ 度的得到的向量相互正交，因此二者内积为 $0$ ，所以：
  • 向量 $(x,y)$ 旋转 $90$ 度和 $270$ 度的向量分别为 $(y,-x)$ 和 $(-y,x)$ ；
• 向量 $(x,y)$ 旋转 $180$ 度： 取反向量 $(-x,-y)$ 即可；
• 向量 $(x,y)$ 左右翻转： $x$ 取反即可，即得到 $(-x,y)$ ；
• 向量 $(x,y)$ 上下翻转： $y$ 取反即可，即得到 $(x,$