# C++ using BFS with pair to solve.

• the basic idea is simple. using the same order to go through the BFS and record each point's `diff_x` and `diff_y` by using the `pair` and for each time of BFS we will construct a `vector<pair<int, int> >`. Note that the same shape islands will have extremely same vectors. Thus we then delete the same vector and get the size.
Though the code will seem a bit long, note that most code can be copyed from the previous problem.
Here is my AC code. I hope it helps.

``````class Solution {
public:
bool isValid(vector<vector<int>>& grid, pair<int, int> &point) {
int row = point.first, col = point.second;
if (row < 0 || col < 0) return false;
if (row >= grid.size()) return false;
return (col < grid[row].size());
}
vector<pair<int, int> > BFS(vector<vector<int>>& grid, vector<vector<bool> >&visited, int row, int col) {
queue<pair<int, int> >q;
visited[row][col] = true;
q.push(pair<int, int>(row, col));
vector<pair<int, int> > shape;
while (!q.empty()) {
auto t = q.front();
q.pop();
pair<int, int> down(t.first + 1, t.second);
pair<int, int> up(t.first - 1, t.second);
pair<int, int> left(t.first, t.second - 1);
pair<int, int> right(t.first, t.second + 1);
if (isValid(grid, down) && grid[t.first + 1][t.second] == 1 && !visited[t.first + 1][t.second]) {
q.push(down);
visited[t.first + 1][t.second] = true;
shape.push_back(pair<int, int>(row - (t.first + 1), col - t.second));
}
if (isValid(grid, up) && grid[t.first - 1][t.second] == 1 && !visited[t.first - 1][t.second]) {
q.push(up);
visited[t.first - 1][t.second] = true;
shape.push_back(pair<int, int>(row - (t.first - 1), col - t.second));
}
if (isValid(grid, left) && grid[t.first][t.second - 1] == 1 && !visited[t.first][t.second - 1]) {
q.push(left);
visited[t.first][t.second - 1] = true;
shape.push_back(pair<int, int>(row - t.first, col - (t.second - 1)));
}
if (isValid(grid, right) && grid[t.first][t.second + 1] == 1 && !visited[t.first][t.second + 1]) {
q.push(right);
visited[t.first][t.second + 1] = true;
shape.push_back(pair<int, int>(row - t.first, col - (t.second + 1)));
}
}
return shape;
}
bool isSame(vector<pair <int, int> > & v1, vector<pair<int, int> > & v2) {
if (v1.size() != v2.size()) return false;
for (int i = 0; i < v1.size(); ++i) {
if (v1[i].first != v2[i].first || v1[i].second != v2[i].second) return false;
}
return true;
}
int diff_shapes(vector<vector<pair<int, int> > > &shapes) {
vector<vector<pair<int, int> > > non_same_shapes;
bool has_the_same = false;
for(int i = 0; i < shapes.size(); ++i) {
has_the_same = false;
for (int j = 0; j < non_same_shapes.size(); ++j) {
if (isSame(shapes[i], non_same_shapes[j])) {
has_the_same = true;
break;
}
}
if (!has_the_same) non_same_shapes.push_back(shapes[i]);
}
return non_same_shapes.size();
}
int numDistinctIslands(vector<vector<int>>& grid) {
vector<vector<bool> > visited(grid.size());
vector<vector<pair<int, int> > > shape;
for (int i = 0; i < visited.size(); ++i) {
visited[i].resize(grid[i].size());
}
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j] == 0) {
visited[i][j] = true;
continue;
}
if (!visited[i][j]) shape.push_back(BFS(grid, visited, i, j));
}
}
return diff_shapes(shape);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.