694. Number of Distinct Islands

本文主要是介绍694. Number of Distinct Islands，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

发现这些题目还是套路深啊！完全不适合我这种不长脑子的人。
题目要求的是不一样的陆地，形状不同，面积不同等。那怎么去确定不同那？
当确定了开始点后，下一步就是遍历四周是不是陆地。那遍历四周都是变换x，y的左边。比如上下左右的顺序。可以把这点陆地的位置相对于起始点的位置的相对位置记录下。
然后把这些形状push到unorder_set里。同样的set就会被hash掉。

class Solution {
public:

vector<pair<int, int>> bfs(int i, int j, vector<vector<int>>& grid)
{
queue<pair<int, int>> myqueue;
vector<int> direcX{-1, 0, 1, 0};
vector<int> direcY{0, 1, 0, -1};
int row = grid.size();
int col = grid[0].size();
vector<pair<int, int>> v;
int startX = i;
int startY = j;

myqueue.push({i, j});

while(!myqueue.empty())
{
pair<int, int> cur = myqueue.front();
myqueue.pop();

int x = cur.first;
int y = cur.second;

for(int i=0;i<4;i++) {
int newx = x + direcX[i];
int newy = y + direcY[i];

if(newx>=0 && newx < row && newy>=0 && newy < col && grid[newx][newy] == 1) {
v.push_back({newx-startX, newy-startY});
grid[newx][newy] =-1;
myqueue.push({newx, newy});
}
}
}

return v;
}

int numDistinctIslands(vector<vector<int>>& grid) {
set<vector<pair<int, int>>> ret;
vector<pair<int, int>> tmp;
int row = grid.size();
int col = grid[0].size();

for(int i =0; i<row; i++) {
for(int j =0; j<col; j++) {
if(grid[i][j] == 1){
grid[i][j] = -1;
tmp = bfs(i, j, grid);
ret.insert(tmp);
}
}
}

return ret.size();
}
};