711. Number of Distinct Islands II

using 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;
    }
}

#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;
    }
}

import 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];
    }
}

var 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;
};

def 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)

package 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()
}

Algorithm

Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.

😎