Сложность: hard
Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.
Пример:
Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1
👨💻 Алгоритм:
1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.
2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.
3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.
😎 Решение:
class Solution {
func numDistinctIslands2(_ grid: [[Int]]) -> Int {
var grid = grid
var uniqueIslands = Set<[[(Int, Int)]]>()
func dfs(_ i: Int, _ j: Int) -> [(Int, Int)] {
var shape = [(Int, Int)]()
var stack = [(i, j)]
while !stack.isEmpty {
let (x, y) = stack.removeLast()
if x >= 0 && x < grid.count && y >= 0 && y < grid[0].count && grid[x][y] == 1 {
grid[x][y] = 0
shape.append((x - i, y - j))
stack.append((x + 1, y))
stack.append((x - 1, y))
stack.append((x, y + 1))
stack.append((x, y - 1))
}
}
return shape
}
func normalize(_ shape: [(Int, Int)]) -> [[(Int, Int)]] {
var shapes = Array(repeating: [(Int, Int)](), count: 8)
for (x, y) in shape {
shapes[0].append((x, y))
shapes[1].append((x, -y))
shapes[2].append((-x, y))
shapes[3].append((-x, -y))
shapes[4].append((y, x))
shapes[5].append((y, -x))
shapes[6].append((-y, x))
shapes[7].append((-y, -x))
}
for i in 0..<8 {
shapes[i].sort(by: { $0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0 })
}
return shapes
}
for i in 0..<grid.count {
for j in 0..<grid[0].count {
if grid[i][j] == 1 {
let shape = dfs(i, j)
let normalizedShape = normalize(shape)
if let minShape = normalizedShape.min(by: { $0.lexicographicallyPrecedes($1) }) {
uniqueIslands.insert(minShape)
}
}
}
}
return uniqueIslands.count
}
}Ставь 👍 и забирай 📚 Базу знаний