# C++, BFS + set, with explanation

• It is straightforward to BFS each island. However, we need a way to encode each island, in order to tell whether they are distinct or not.

``````For each island, a vector is used to store the relative locations of every point to the starting point.
If the starting point is (row, col), then for any point (r, c), a key value = (r-row)*50+c-col is
added into the island vector.
``````

We can use a set (ordered set or tree set) to only keep unique vectors, and return its size. Another way is to sort and count all the unique island vectors.

``````class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
set<vector<int>> islands;
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) islands.insert(helper(grid, i, j));
}
}
return islands.size();
}
private:
vector<int> helper(vector<vector<int>>& grid, int row, int col) {
int m = grid.size(), n = grid[0].size();
vector<int> island;
queue<pair<int, int>> myq;
myq.push({row, col});
grid[row][col] = 2;
vector<int> dir = {-1,0,1,0,-1};
while (!myq.empty()) {
int z = myq.front().first, x = myq.front().second;
myq.pop();
for (int i = 0; i < 4; i++) {
int r = z+dir[i], c = x+dir[i+1];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
grid[r][c] = 2;
myq.push({r,c});
island.push_back((r-row)*50+c-col);
}
}
}
return island;
}
};
``````

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