C++ using BFS with pair to solve.


  • 0
    G

    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);
        }
    };
    

Log in to reply
 

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