PHP Backend | YeaHub

#ЛитКод
Задача: 711. Number of Distinct Islands II

Вам дана двоичная матричная сетка 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⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.

😎 Решение:

function numDistinctIslands2($grid) {
    $uniqueIslands = [];
    
    for ($i = 0; $i < count($grid); $i++) {
        for ($j = 0; $j < count($grid[0]); $j++) {
            if ($grid[$i][$j] == 1) {
                $shape = [];
                dfs($grid, $i, $j, $i, $j, $shape);
                $uniqueIslands[normalize($shape)] = true;
            }
        }
    }
    
    return count($uniqueIslands);
}

function dfs(&$grid, $i, $j, $baseI, $baseJ, &$shape) {
    if ($i < 0 || $i >= count($grid) || $j < 0д  

Задача

: 

711. Number of Di$grid[$i][$j]

 == 0) {
        return;
    }
    $grid[$i][$j] = 0;
    $shape[] = [$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);
}

function normalize($shape) {
    $shapes = array_fill(0, 8, []);
    foreach ($shape as $p) {
        $x = $p[0];
        $y = $p[1];
        $shapes[0][] = [$x, $y];
        $shapes[1][] = [$x, -$y];
        $shapes[2][] = [-$x, $y];
        $shapes[3][] = [-$x, -$y];
        $shapes[4][] = [$y, $x];
        $shapes[5][] = [$y, -$x];
        $shapes[6][] = [-$y, $x];
        $shapes[7][] = [-$y, -$x];
    }
    foreach ($shapes as &$s) {
        sort($s);
    }
    $minShape = implode(",", array_map(function($p) { return implode(",", $p); }, $shapes[0]));
    foreach ($shapes as $s) {
        $sStr = implode(";", array_map(function($p) { return implode(",", $p); }, $s));
        $minShape = min($minShape, $sStr);
    }
    return $minShape;
}

👉Новости 👉База вопросов

Please open Telegram to view this post

VIEW IN TELEGRAM

www.tgoop.com/yeahub_php_backend/178

74 viewsApr 23 at 15:01

#ЛитКод
Задача: 711. Number of Distinct Islands II

Вам дана двоичная матричная сетка 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

function numDistinctIslands2($grid) {
    $uniqueIslands = [];
    
    for ($i = 0; $i < count($grid); $i++) {
        for ($j = 0; $j < count($grid[0]); $j++) {
            if ($grid[$i][$j] == 1) {
                $shape = [];
                dfs($grid, $i, $j, $i, $j, $shape);
                $uniqueIslands[normalize($shape)] = true;
            }
        }
    }
    
    return count($uniqueIslands);
}

function dfs(&$grid, $i, $j, $baseI, $baseJ, &$shape) {
    if ($i < 0 || $i >= count($grid) || $j < 0д  

Задача

: 

711. Number of Di$grid[$i][$j]

 == 0) {
        return;
    }
    $grid[$i][$j] = 0;
    $shape[] = [$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);
}

function normalize($shape) {
    $shapes = array_fill(0, 8, []);
    foreach ($shape as $p) {
        $x = $p[0];
        $y = $p[1];
        $shapes[0][] = [$x, $y];
        $shapes[1][] = [$x, -$y];
        $shapes[2][] = [-$x, $y];
        $shapes[3][] = [-$x, -$y];
        $shapes[4][] = [$y, $x];
        $shapes[5][] = [$y, -$x];
        $shapes[6][] = [-$y, $x];
        $shapes[7][] = [-$y, -$x];
    }
    foreach ($shapes as &$s) {
        sort($s);
    }
    $minShape = implode(",", array_map(function($p) { return implode(",", $p); }, $shapes[0]));
    foreach ($shapes as $s) {
        $sStr = implode(";", array_map(function($p) { return implode(",", $p); }, $s));
        $minShape = min($minShape, $sStr);
    }
    return $minShape;
}