用每个块中的所有点的坐标来记录每个块,注意要归一化,即每个点减去最小点的横纵坐标
typedef pair<int,int> PII;
const int N=55;
PII q[N*N];
#define x first
#define y second
class Solution {
public:
int top;
vector<vector<int>>g;
int n,m;
int numDistinctIslands(vector<vector<int>>& grid) {
int res=0;
g=grid;
n=g.size(),m=g[0].size();
set<vector<PII>>S;
memset(q,0,sizeof q);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j])
{
int minx=N,miny=N;
top=0;
dfs(i,j,minx,miny);
vector<PII>t;
sort(q,q+top);
for(int i=0;i<top;i++)
t.push_back({q[i].x-minx,q[i].y-miny});
S.insert(t);
}
return S.size();
}
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void dfs(int x,int y,int &minx,int &miny)
{
minx=min(minx,x);
miny=min(miny,y);
q[top++]={x,y};
g[x][y]=0;
for(int i=0;i<4;i++)
{
int a=x+dx[i];
int b=y+dy[i];
if(a>=0 && a<n && b>=0 && b<m && g[a][b])
dfs(a,b,minx,miny);
}
}
};
如果岛屿相等包含旋转和对称的情况,那么可以用一个哈希函数来记录形状
typedef pair<int,int> PII;
const int N=55;
PII q[N*N];
#define x first
#define y second
class Solution {
public:
int top;
vector<vector<int>>g;
int n,m;
int numDistinctIslands(vector<vector<int>>& grid) {
int res=0;
g=grid;
n=g.size(),m=g[0].size();
set<int>S;
memset(q,0,sizeof q);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j])
{
top=0;
dfs(i,j);
double t=get_hash();
S.insert(t);
}
return S.size();
}
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void dfs(int x,int y)
{
q[top++]={x,y};
g[x][y]=0;
for(int i=0;i<4;i++)
{
int a=x+dx[i];
int b=y+dy[i];
if(a>=0 && a<n && b>=0 && b<m && g[a][b])
dfs(a,b);
}
}
double get_hash()
{
double sum=0;
for(int i=0;i<top;i++)
for(int j=i+1;j<top;j++)
sum+=get_dist(q[i],q[j]);
return sum;
}
double get_dist(PII a, PII b)
{
double dx=a.x-b.x;
double dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
};