力扣第 711 题
题目
给定一个 m x n 二进制数组表示的网格 grid ，一个岛屿由 四连通 （上、下、左、右四个方向）的 1 组成（代表陆地）。你可以认为网格的四周被海水包围。
如果两个岛屿的形状相同，或者通过旋转（顺时针旋转 90°，180°，270°）、翻转（左右翻转、上下翻转）后形状相同，那么就认为这两个岛屿是相同的。
返回 这个网格中形状 不同 的岛屿的数量 。
示例 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
提示:
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j] 不是 0 就是 1.
分析
- 考虑对岛屿哈希，以最左上角为原点，所有网格的相对坐标的集合作为哈希值
- 可以取所有旋转翻转操作的最小哈希值作为 key
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution:
def numDistinctIslands2(self, grid: List[List[int]]) -> int:
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
flip_directions = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
m, n = len(grid), len(grid[0])
def get_shape(shape):
def encode(shape):
x, y = shape[0]
return "".join(str(i - x) + ":" + str(j - y) for i, j in shape)
shapes = [[(i * a, j * b) for i, j in shape] for a, b in flip_directions]
shapes += [[(j, i) for i, j in s] for s in shapes]
return min(encode(sorted(s)) for s in shapes)
def dfs(i, j):
grid[i][j] *= -1
shape = [(i, j)]
for dx, dy in directions:
x, y = i + dx, j + dy
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
shape += dfs(x, y)
return shape
islands = set()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
islands.add(get_shape(dfs(i, j)))
return len(islands)
|
223 ms