# Simple C++ BFS 39ms

• ``````class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> visited(m, vector<int>(n, 0));
vector<vector<vector<int> > > shape;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1 && visited[i][j] == 0) {
vector<vector<int>> path = bfs(grid, i, j, visited);
int k = 0;
while (k < shape.size()) {
if (isSame(shape[k], path)) break;
++k;
}
if (shape.empty() || k == shape.size()) shape.push_back(path);
}
}
}
return shape.size();
}
private:
vector<vector<int>> bfs(vector<vector<int>>& grid, int i, int j, vector<vector<int>>& visited) {
int level = 0;
vector<vector<int>> path;
queue<pair<int, int>> levelQ;
levelQ.push({i, j});
visited[i][j] = 1;
while(!levelQ.empty()) {
int curSize = levelQ.size();
while (curSize--) {
int m = levelQ.front().first;
int n = levelQ.front().second;
levelQ.pop();
if (m - 1 >= 0 && grid[m-1][n] == 1 && visited[m-1][n] == 0) {
levelQ.push({m - 1, n});
visited[m-1][n] = 1;
path.push_back({level, curSize, -1, 0});
}
if (m + 1 < grid.size() && grid[m+1][n] == 1 && visited[m+1][n] == 0) {
levelQ.push({m + 1, n});
visited[m+1][n] = 1;
path.push_back({level, curSize, 1, 0});
}
if (n - 1 >= 0 && grid[m][n-1] == 1 && visited[m][n-1] == 0) {
levelQ.push({m, n - 1});
visited[m][n-1] = 1;
path.push_back({level, curSize, 0, -1});
}
if (n + 1 < grid[0].size() && grid[m][n+1] == 1 && visited[m][n+1] == 0) {
levelQ.push({m, n + 1});
visited[m][n+1] = 1;
path.push_back({level, curSize, 0, 1});
}
}
++level;
}
return path;
}

bool isSame(vector<vector<int> >& p1, vector<vector<int> >& p2) {
if (p1.size() != p2.size()) return false;
for (int i = 0; i < p1.size(); ++i) {
for (int j = 0; j < p1[0].size(); ++j)
if (p1[i][j] != p2[i][j]) return false;
}
return true;
}
};
``````

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