Consise C++ solution, using DFS +sorting to find canonical representation for each island


  • 8
    E

    After we get coordinates for an island, compute all possible rotations/reflections (https://en.wikipedia.org/wiki/Dihedral_group) of it and then sort them using the default comparison. The first representation in this order is then the canonical one.

    class Solution {
    public:
        map<int, vector<pair<int,int>>> mp;
        
        void dfs(int r, int c, vector<vector<int>> &g, int cnt) {
            if ( r < 0 || c < 0 || r >= g.size() || c >= g[0].size()) return;
            if (g[r][c] != 1) return;
            g[r][c] = cnt;
            mp[cnt].push_back({r,c});
            dfs(r+1,c,g,cnt);
            dfs(r-1,c,g,cnt);
            dfs(r,c+1,g,cnt);
            dfs(r,c-1,g,cnt);
        }
        
        vector<pair<int,int>> norm(vector<pair<int,int>> v) {
            vector<vector<pair<int,int>>> s(8);
            // compute rotations/reflections.
            for (auto p:v) {
                int x = p.first, y = p.second;
                s[0].push_back({x,y});
                s[1].push_back({x,-y});
                s[2].push_back({-x,y});
                s[3].push_back({-x,-y});
                s[4].push_back({y,-x});
                s[5].push_back({-y,x});
                s[6].push_back({-y,-x});
                s[7].push_back({y,x});
            }
            for (auto &l:s) sort(l.begin(),l.end());
            for (auto &l:s) {
                for (int i = 1; i < v.size(); ++i) 
                    l[i] = {l[i].first-l[0].first, l[i].second - l[0].second};
                l[0] = {0,0};
            }
            sort(s.begin(),s.end());
            return s[0];
        }
        
        int numDistinctIslands2(vector<vector<int>>& g) {
            int cnt = 1;
            set<vector<pair<int,int>>> s;
            for (int i = 0; i < g.size(); ++i) for (int j = 0; j < g[i].size(); ++j) if (g[i][j] == 1) {
                dfs(i,j,g, ++cnt);
                s.insert(norm(mp[cnt]));
            }
            
            return s.size();
        }
    };
    

  • 0
    T

    Can you provide more detailed explanations about your algorithms?


  • 1
    E

    @tiandiao123 Which parts do you need more explanation?


  • 0
    T

    @dickchimney I am confused about the how you design your norm function. What usages of the norm function? Thank you!


  • 2
    E

    @tiandiao123 : Each island has 8 equivalent arrangements, which can be formed by combinations of reflections/rotations. So I compute all those arrangements (s[0], s[1], .., s[7]) and sort them using default ordering, and return the first arrangement. Equivalent island has the same set of equivalent arrangements so the norm function return the same value.


  • 0
    W

    @elastico
    Thank you for writing concisely code for this problem.

    1. for (auto &l:s) sort(l.begin(),l.end());

    "I" in for-loop is vector<pair<int,int>>, meaning it is a container with lots of pairs<x, y>.
    I failed to understand this line even with help of Google. I am not sure how sort in C++ will order these pairs.

    sort(s.begin(),s.end());
    I do not understand the above line as well.

    1. You said: Each island has 8 equivalent arrangements, which can be formed by combinations of reflections/rotations. So I compute all those arrangements (s[0], s[1], .., s[7]) and sort them using default ordering, and return the first arrangement. Equivalent island has the same set of equivalent arrangements so the norm function return the same value.

    I understand that you generated 8 replicates of the original island via reflection and rotation. But I wonder if your code can identify two islands of the same shape when they are reflected/rotated and then shifted by a few grids.
    Below is an example:
    11100
    10001
    01001
    01110

    two islands 1
    1 1 1

    Thanks for helping me understand your solution.


  • 1
    E

    @wwzzgg 1. The first sort is to make sure that each replica has cells coordinates sorted up-to-down and then left-to-right. C++ sort pair of ints lexicographically by default. It doesn't matter the specific order in this case, each replica just needs to be sorted in the same way. After that the replicas are sorted among each other. It doesn't matter how are they sorted, we just need to use the same sort criteria all the time. In this case, each island is mapped to the first replica in the sorted order, so if two islands having the same set of replicas, they are mapped to the same thing.

    1. In this line:
    for (int i = 1; i < v.size(); ++i) 
        l[i] = {l[i].first-l[0].first, l[i].second - l[0].second};
    

    each cell's coordinates in an island are replaced by their displacement compared to the first cell (in a consistent sort order). This is invariant with respect to shifting.


  • 0
    Z

    Similar idea. Java version

    class Solution {
        int[][] dirs={{-1,0}, {1,0}, {0,-1}, {0,1}};
        int[][] trans={{1,1}, {1,-1}, {-1,1}, {-1,-1}};
        
        public int numDistinctIslands2(int[][] grid) {
            if (grid==null || grid.length==0 || grid[0].length==0) return 0;
            int m=grid.length, n=grid[0].length;
            Set<String>islands=new HashSet<>();
            
            for (int i=0;i<m;i++){
                for (int j=0;j<n;j++){
                    if (grid[i][j]==1){
                        List<int[]> cells=new ArrayList<>();
                        dfs(grid, i, j, cells);
                        String key=norm(cells);
                        islands.add(key);
                    }
                }
            }
            return islands.size();
        }
        
        private void dfs(int[][] grid, int i, int j, List<int[]> cells){
            cells.add(new int[]{i, j});
            grid[i][j]=-1;
            
            for (int[] dir:dirs){
                int x=i+dir[0];
                int y=j+dir[1];
                if (x>=0 && x<grid.length && y>=0 && y<grid[0].length && grid[x][y]==1)
                    dfs(grid, x, y, cells);
            }
        }
    
        private String norm(List<int[]>cells){
            List<String> forms=new ArrayList<>();
            // generate the 8 different transformations
            // (x, y), (x, -y), (-x, y), (-x, -y)
            // (y, x), (-y, x), (y, -x), (-y, -x)
            for (int[] ts:trans){
                List<int[]> list1=new ArrayList<>();
                List<int[]> list2=new ArrayList<>();
                for (int[] cell:cells){
                    list1.add(new int[]{cell[0]*ts[0], cell[1]*ts[1]});
                    list2.add(new int[]{cell[1]*ts[1], cell[0]*ts[0]});
                }
                forms.add(getKey(list1));
                forms.add(getKey(list2));
            }
            
            // sort the keys: take the first one as the representative key
            Collections.sort(forms);
            return forms.get(0);
        }
        
        private String getKey(List<int[]>cells){
            // sort the cells before generate the key
            Collections.sort(cells, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    if (a[0]!=b[0]){
                        return a[0]-b[0];
                    }else{
                        return a[1]-b[1];
                    }
                }
            });
    
            StringBuilder sb=new StringBuilder();
            int x=cells.get(0)[0], y=cells.get(0)[1];
            for (int[] cell:cells)
                sb.append((cell[0]-x)+":"+(cell[1]-y)+":");
            
            return sb.toString();
        }
    }
    
    

Log in to reply
 

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