classSolution{public:intnumDistinctIslands2(vector<vector<int>>&grid){constintm=grid.size();constintn=grid[0].size();set<vector<pair<int,int>>>islands;// All different shape islandsvector<vector<bool>>seen(m,vector<bool>(n));for(inti=0;i<m;++i)for(intj=0;j<n;++j){vector<pair<int,int>>island;dfs(grid,i,j,seen,island);if(!island.empty())islands.insert(normalize(island));}returnislands.size();}private:voiddfs(constvector<vector<int>>&grid,inti,intj,vector<vector<bool>>&seen,vector<pair<int,int>>&island){if(i<0||i==grid.size()||j<0||j==grid[0].size())return;if(grid[i][j]==0||seen[i][j])return;seen[i][j]=true;island.emplace_back(i,j);dfs(grid,i+1,j,seen,island);dfs(grid,i-1,j,seen,island);dfs(grid,i,j+1,seen,island);dfs(grid,i,j-1,seen,island);}vector<pair<int,int>>normalize(constvector<pair<int,int>>&island){// points[i] := 8 different rotations/reflections of islandvector<vector<pair<int,int>>>points(8);for(constauto&[i,j]:island){points[0].emplace_back(i,j);points[1].emplace_back(i,-j);points[2].emplace_back(-i,j);points[3].emplace_back(-i,-j);points[4].emplace_back(j,i);points[5].emplace_back(j,-i);points[6].emplace_back(-j,i);points[7].emplace_back(-j,-i);}for(vector<pair<int,int>>&p:points)sort(begin(p),end(p));// Normalize each p by minus p[1:] w/ p[0]for(vector<pair<int,int>>&p:points){for(inti=1;i<island.size();++i)p[i]={p[i].first-p[0].first,p[i].second-p[0].second};p[0]={0,0};}sort(begin(points),end(points));returnpoints[0];}};
classSolution{publicintnumDistinctIslands2(int[][]grid){finalintm=grid.length;finalintn=grid[0].length;Set<List<Pair<Integer,Integer>>>islands=newHashSet<>();// All different shape islandsboolean[][]seen=newboolean[m][n];for(inti=0;i<m;++i)for(intj=0;j<n;++j){List<Pair<Integer,Integer>>island=newArrayList<>();dfs(grid,i,j,seen,island);if(!island.isEmpty())islands.add(normalize(island));}returnislands.size();}privatevoiddfs(int[][]grid,inti,intj,boolean[][]seen,List<Pair<Integer,Integer>>island){if(i<0||i==grid.length||j<0||j==grid[0].length)return;if(grid[i][j]==0||seen[i][j])return;seen[i][j]=true;island.add(newPair<>(i,j));dfs(grid,i+1,j,seen,island);dfs(grid,i-1,j,seen,island);dfs(grid,i,j+1,seen,island);dfs(grid,i,j-1,seen,island);}privateList<Pair<Integer,Integer>>normalize(List<Pair<Integer,Integer>>island){// points[i] := 8 different rotations/reflections of islandPair<Integer,Integer>[][]points=newPair[8][island.size()];for(intk=0;k<island.size();++k){finalinti=island.get(k).getKey();finalintj=island.get(k).getValue();points[0][k]=newPair<>(i,j);points[1][k]=newPair<>(i,-j);points[2][k]=newPair<>(-i,j);points[3][k]=newPair<>(-i,-j);points[4][k]=newPair<>(j,i);points[5][k]=newPair<>(j,-i);points[6][k]=newPair<>(-j,i);points[7][k]=newPair<>(-j,-i);}for(Pair<Integer,Integer>[]p:points)Arrays.sort(p,(a,b)->a.getKey()==b.getKey()?a.getValue()-b.getValue():a.getKey()-b.getKey());// Normalize each p by minus p[1:] w/ p[0]for(Pair<Integer,Integer>[]p:points){for(inti=1;i<island.size();++i)p[i]=newPair<>(p[i].getKey()-p[0].getKey(),p[i].getValue()-p[0].getValue());p[0]=newPair<>(0,0);}Arrays.sort(points,newComparator<Pair<Integer,Integer>[]>(){@Overridepublicintcompare(Pair<Integer,Integer>[]a,Pair<Integer,Integer>[]b){for(inti=0;i<a.length;++i){if(a[i].getKey()!=b[i].getKey())returna[i].getKey()-b[i].getKey();if(a[i].getValue()!=b[i].getValue())returna[i].getValue()-b[i].getValue();}return0;}});returnArrays.asList(points[0]);}}
classSolution:defnumDistinctIslands2(self,grid:List[List[int]])->int:seen=set()defdfs(i:int,j:int):ifi<0ori==len(grid)orj<0orj==len(grid[0]):returnifgrid[i][j]==0or(i,j)inseen:returnseen.add((i,j))island.append((i,j))dfs(i+1,j)dfs(i-1,j)dfs(i,j+1)dfs(i,j-1)defnormalize(island:List[tuple])->List[tuple]:# points[i] := 8 different rotations/reflections of islandpoints=[[]for_inrange(8)]fori,jinisland:points[0].append((i,j))points[1].append((i,-j))points[2].append((-i,j))points[3].append((-i,-j))points[4].append((j,i))points[5].append((j,-i))points[6].append((-j,i))points[7].append((-j,-i))points=[sorted(p)forpinpoints]# Normalize each p by minus p[1:] w/ p[0]forpinpoints:foriinrange(1,len(island)):p[i]=(p[i][0]-p[0][0],p[i][1]-p[0][1])p[0]=(0,0)returnsorted(points)[0]islands=set()# All different shape islandsforiinrange(len(grid)):forjinrange(len(grid[0])):island=[]dfs(i,j)ifisland:islands.add(frozenset(normalize(island)))returnlen(islands)