Simple C++ BFS 39ms


  • 0
    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;
        }
    };
    

Log in to reply
 

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