My solution using BFS and set


  • 0
    Z

    my solution using BFS and set.
    similar as the other problem for count the number of islands, use BFS approach for that. the way to avoid double counting the islands that have the same shape is to store the island in a vector list. each element of the list is the offset of the cell to its top left corner, so islands that have the same shape will have the same vector. When insert the island into the set, duplicated shape is automatically removed by set.

    static int offset[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    bool myCompare(pair<int, int> &A, pair<int, int> &B) {
        if (A.first < B.first) {
            return true;
        } else if (A.first == B.first) {
            return (A.second < B.second);
        } else {
            return false;
        }
    }
    
    class Solution {
            
        vector<pair<int, int>> BFS(vector<vector<int>> &grid, vector<vector<bool>> &visited, int r, int c) {
            int row = grid.size();
            int col = grid[0].size();
            queue<pair<int, int>> q;
            vector<pair<int, int>> ans;
            
            q.push(make_pair(r, c));
            visited[r][c] = true;
            ans.push_back(make_pair(0, 0));
            
            while (!q.empty()) {
                auto &it = q.front();
                for (int k = 0; k < 4; k ++) {
                    int r_next = it.first + offset[k][0];
                    int c_next = it.second + offset[k][1];
                    if ((r_next < 0) || (r_next >= row)) continue;
                    if ((c_next < 0) || (c_next >= col)) continue;
                    
                    if ((grid[r_next][c_next] == 1) && (!visited[r_next][c_next])) {
                        q.push(make_pair(r_next, c_next));
                        visited[r_next][c_next] = true;
                        ans.push_back(make_pair(r_next-r, c_next-c));
                    }
                }
                q.pop();
            }
            
            sort(ans.begin(), ans.end(), myCompare);
            
            return ans;
        }
        
    public:
        int numDistinctIslands(vector<vector<int>>& grid) {
            int row = grid.size();
            if (row == 0) return 0;
            int col = grid[0].size();
            vector<vector<bool>> visited(row, vector<bool>(col, false));
            int ans = 0;
            set<vector<pair<int, int>>> islands;
            
            for (int r = 0;  r < row; r ++) {
                for (int c = 0; c < col; c ++) {
                    if ((grid[r][c] == 1) && (!visited[r][c])) {
                        vector<pair<int, int>> island = BFS(grid, visited, r, c);
                        islands.insert(island);
                    }
                }
            }
            
            return islands.size();
        }
    };
    

Log in to reply
 

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