Задача: 711. Number of Distinct Islands II
Сложность: 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 {
    fun numDistinctIslands2(grid: Array<IntArray>): Int {
        val uniqueIslands = mutableSetOf<String>()
        
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                if (grid[i][j] == 1) {
                    val shape = mutableListOf<Pair<Int, Int>>()
                    dfs(grid, i, j, i, j, shape)
                    uniqueIslands.add(normalize(shape))
                }
            }
        }
        
        return uniqueIslands.size
    }
    
    private fun dfs(grid: Array<IntArray>, i: Int, j: Int, baseI: Int, baseJ: Int, shape: MutableList<Pair<Int, Int>>) {
        if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == 0) {
            return
        }
        grid[i][j] = 0
        shape.add(Pair(i - baseI, j - baseJ))
        dfs(grid, i + 1, j, baseI, baseJ, shape)
        dfs(grid, i - 1, j, baseI, baseJ, shape)
        dfs(grid, i, j + 1, baseI, baseJ, shape)
        dfs(grid, i, j - 1, baseI, baseJ, shape)
    }
    
    private fun normalize(shape: List<Pair<Int, Int>>): String {
        val shapes = List(8) { mutableListOf<Pair<Int, Int>>() }
        for ((x, y) in shape) {
            shapes[0].add(Pair(x, y))
            shapes[1].add(Pair(x, -y))
            shapes[2].add(Pair(-x, y))
            shapes[3].add(Pair(-x, -y))
            shapes[4].add(Pair(y, x))
            shapes[5].add(Pair(y, -x))
            shapes[6].add(Pair(-y, x))
            shapes[7].add(Pair(-y, -x))
        }
        for (s in shapes) {
            s.sortWith(compareBy({ it.first }, { it.second }))
        }
        val minShape = shapes.minByOrNull { it.toString() }!!
        return minShape.joinToString(";") { "${it.first},${it.second}" }
    }
}

Ставь 👍 и забирай 📚 Базу знаний