711. Number of Distinct Islands II
leetcode hard
#array#csharp#graph#hard#hash-table#leetcode#matrix#sort#string
Task
Вам дана двоичная матричная сетка 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
C# solution
matched/originalusing System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int NumDistinctIslands2(int[][] grid) {
var uniqueIslands = new HashSet<string>();
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[0].Length; j++) {
if (grid[i][j] == 1) {
var shape = new List<(int, int)>();
Dfs(grid, i, j, i, j, shape);
uniqueIslands.Add(Normalize(shape));
}
}
}
return uniqueIslands.Count;
}
private void Dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<(int, int)> shape) {
if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || grid[i][j] == 0) {
return;
}
grid[i][j] = 0;
shape.Add((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 string Normalize(List<(int, int)> shape) {
var shapes = new List<List<(int, int)>>();
for (int i = 0; i < 8; i++) {
shapes.Add(new List<(int, int)>());
}
foreach (var (x, y) in shape) {
shapes[0].Add((x, y));
shapes[1].Add((x, -y));
shapes[2].Add((-x, y));
shapes[3].Add((-x, -y));
shapes[4].Add((y, x));
shapes[5].Add((y, -x));
shapes[6].Add((-y, x));
shapes[7].Add((-y, -x));
}
foreach (var s in shapes) {
s.Sort();
}
string minShape = string.Join(";", shapes[0].Select(p => $"{p.Item1},{p.Item2}"));
foreach (var s in shapes) {
string sStr = string.Join(";", s.Select(p => $"{p.Item1},{p.Item2}"));
if (string.Compare(sStr, minShape, StringComparison.Ordinal) < 0) {
minShape = sStr;
}
}
return minShape;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int NumDistinctIslands2(int[][] grid) {
var uniqueIslands = new HashSet<string>();
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
var shape = new List<(int, int)>();
Dfs(grid, i, j, i, j, shape);
uniqueIslands.push_back(Normalize(shape));
}
}
}
return uniqueIslands.size();
}
private void Dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<(int, int)> shape) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {
return;
}
grid[i][j] = 0;
shape.push_back((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 string Normalize(List<(int, int)> shape) {
var shapes = new List<List<(int, int)>>();
for (int i = 0; i < 8; i++) {
shapes.push_back(new List<(int, int)>());
}
foreach (var (x, y) in shape) {
shapes[0].push_back((x, y));
shapes[1].push_back((x, -y));
shapes[2].push_back((-x, y));
shapes[3].push_back((-x, -y));
shapes[4].push_back((y, x));
shapes[5].push_back((y, -x));
shapes[6].push_back((-y, x));
shapes[7].push_back((-y, -x));
}
foreach (var s in shapes) {
s.Sort();
}
string minShape = string.Join(";", shapes[0].Select(p => $"{p.Item1},{p.Item2}"));
foreach (var s in shapes) {
string sStr = string.Join(";", s.Select(p => $"{p.Item1},{p.Item2}"));
if (string.Compare(sStr, minShape, StringComparison.Ordinal) < 0) {
minShape = sStr;
}
}
return minShape;
}
}Java solution
matched/originalimport java.util.*;
public class Solution {
public int numDistinctIslands2(int[][] grid) {
Set<String> uniqueIslands = new HashSet<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
List<int[]> shape = new ArrayList<>();
dfs(grid, i, j, i, j, shape);
uniqueIslands.add(normalize(shape));
}
}
}
return uniqueIslands.size();
}
private void dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<int[]> shape) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
return;
}
grid[i][j] = 0;
shape.add(new int[] {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 String normalize(List<int[]> shape) {
List<List<int[]>> shapes = new ArrayList<>();
for (int i = 0; i < 8; i++) {
shapes.add(new ArrayList<>());
}
for (int[] point : shape) {
int x = point[0], y = point[1];
shapes.get(0).add(new int[] {x, y});
shapes.get(1).add(new int[] {x, -y});
shapes.get(2).add(new int[] {-x, y});
shapes.get(3).add(new int[] {-x, -y});
shapes.get(4).add(new int[] {y, x});
shapes.get(5).add(new int[] {y, -x});
shapes.get(6).add(new int[] {-y, x});
shapes.get(7).add(new int[] {-y, -x});
}
for (List<int[]> s : shapes) {
s.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
}
String[] shapesStr = new String[8];
for (int i = 0; i < 8; i++) {
shapesStr[i] = shapes.get(i).toString();
}
Arrays.sort(shapesStr);
return shapesStr[0];
}
}JavaScript solution
matched/originalvar numDistinctIslands2 = function(grid) {
const dfs = (i, j) => {
const shape = [];
const stack = [[i, j]];
while (stack.length) {
const [x, y] = stack.pop();
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] === 1) {
grid[x][y] = 0;
shape.push([x - i, y - j]);
stack.push([x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]);
}
}
return shape;
};
const normalize = (shape) => {
const shapes = Array.from({ length: 8 }, () => []);
for (const [x, y] of shape) {
shapes[0].push([x, y]);
shapes[1].push([x, -y]);
shapes[2].push([-x, y]);
shapes[3].push([-x, -y]);
shapes[4].push([y, x]);
shapes[5].push([y, -x]);
shapes[6].push([-y, x]);
shapes[7].push([-y, -x]);
}
for (const s of shapes) {
s.sort(([a, b], [c, d]) => a === c ? b - d : a - c);
}
return shapes.reduce((min, s) => {
return JSON.stringify(s) < JSON.stringify(min) ? s : min;
});
};
const uniqueIslands = new Set();
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
const shape = dfs(i, j);
uniqueIslands.add(JSON.stringify(normalize(shape)));
}
}
}
return uniqueIslands.size;
};Python solution
matched/originaldef numDistinctIslands2(grid):
def dfs(i, j):
shape = []
stack = [(i, j)]
while stack:
x, y = stack.pop()
if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
grid[x][y] = 0
shape.append((x - i, y - j))
stack.extend([(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)])
return shape
def normalize(shape):
shapes = [[] for _ in range(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 s in shapes:
s.sort()
return min(shapes)
unique_islands = set()
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
shape = dfs(i, j)
unique_islands.add(tuple(normalize(shape)))
return len(unique_islands)Go solution
matched/originalpackage main
import (
"sort"
"strconv"
"strings"
)
func numDistinctIslands2(grid [][]int) int {
uniqueIslands := make(map[string]struct{})
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == 1 {
shape := [][]int{}
dfs(grid, i, j, i, j, &shape)
uniqueIslands[normalize(shape)] = struct{}{}
}
}
}
return len(uniqueIslands)
}
func dfs(grid [][]int, i, j, baseI, baseJ int, shape *[][]int) {
if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == 0 {
return
}
grid[i][j] = 0
*shape = append(*shape, []int{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)
}
func normalize(shape [][]int) string {
shapes := make([][][]int, 8)
for i := range shapes {
shapes[i] = [][]int{}
}
for _, p := range shape {
x, y := p[0], p[1]
shapes[0] = append(shapes[0], []int{x, y})
shapes[1] = append(shapes[1], []int{x, -y})
shapes[2] = append(shapes[2], []int{-x, y})
shapes[3] = append(shapes[3], []int{-x, -y})
shapes[4] = append(shapes[4], []int{y, x})
shapes[5] = append(shapes[5], []int{y, -x})
shapes[6] = append(shapes[6], []int{-y, x})
shapes[7] = append(shapes[7], []int{-y, -x})
}
for i := range shapes {
sort.Slice(shapes[i], func(a, b int) bool {
if shapes[i][a][0] == shapes[i][b][0] {
return shapes[i][a][1] < shapes[i][b][1]
}
return shapes[i][a][0] < shapes[i][b][0]
})
}
minShape := shapeToString(shapes[0])
for _, s := range shapes {
shapeStr := shapeToString(s)
if shapeStr < minShape {
minShape = shapeStr
}
}
return minShape
}
func shapeToString(shape [][]int) string {
var sb strings.Builder
for _, p := range shape {
sb.WriteString(strconv.Itoa(p[0]))
sb.WriteString(",")
sb.WriteString(strconv.Itoa(p[1]))
sb.WriteString(";")
}
return sb.String()
}Explanation
Algorithm
Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.
Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.
Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.
😎