Straightforward C++ solution, using DFS and generate all possible shapes for islands.


  • 0
    L

    The solution takes the idea that every island is located in one rectangle, so when find the matrix that exactly contains the island, we could use a string consists of 0s and 1s to represent the shape of the island. For example:
    01
    11
    so we first have "0111"(at end of line add a unique character to indicate the end), then we could generate other shapes after some rotation or reflection and store all the unique shapes. The island with the same string must have the same shape.
    And to generate all the possible strings of shapes after rotation or reflection, it's the different ways of traversing the matrix. Start from each corner of the matrix, we have two directions, therefore in total we will have at most 8 different strings of shapes.

    Overall, this solution is pretty straightforward, using the hash one will be more efficient both for time and space.

    class Solution {
    public:
        int m, n;
        vector<int> dirs = {0, 1, 0, -1, 0};
        set<string> rec; // record of all possible island shapes
        
        int numDistinctIslands2(vector<vector<int>>& grid) {
            m = grid.size(), n = m > 0 ? grid[0].size() : 0;
            if(m == 0 || n == 0) return 0;
            int count = 0;
            for(int i = 0; i < m; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(grid[i][j] == 1) {
                        bool found = getShape(grid, i, j);
                        if(found) ++count;
                    }
                }
            }
            return count;
        }
        
        bool getShape(vector<vector<int>>& grid, int x, int y) {
            queue<pair<int, int>> que;
            que.push({x, y});
            grid[x][y] = 2;
            int li = x, lj = y, ri = x, rj = y;
            while(!que.empty()) {
                auto p = que.front();
                que.pop();
                for(int k = 0; k < 4; ++k) {
                    int i = p.first + dirs[k];
                    int j = p.second + dirs[k+1];
                    if(i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) {
                        que.push({i, j});
                        grid[i][j] = 2;
                        li = min(li, i);
                        lj = min(lj, j);
                        ri = max(ri, i);
                        rj = max(rj, j);
                    }
                }
            }
            string s1 = ""; // original
            for(int i = li; i <= ri; ++i) {
                for(int j = lj; j <= rj; ++j) {
                    if(grid[i][j] == 2) s1 += "1";
                    else s1 += "0";
                }
                s1 += "*";
            }
            if(rec.find(s1) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            
            string s2 = ""; // rotate 90 degree
            for(int j = lj; j <= rj; ++j) {
                for(int i = ri; i >= li; --i) {
                    if(grid[i][j] == 2) s2 += "1";
                    else s2 += "0";
                }
                s2 += "*";
            }
            if(rec.find(s2) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            
            string s3 = ""; // rotate 180 degree
            for(int i = ri; i >= li; --i) {
                for(int j = rj; j >= lj; --j) {
                    if(grid[i][j] == 2) s3 += "1";
                    else s3 += "0";
                }
                s3 += "*";
            }
            if(rec.find(s3) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            
            string s4 = ""; // rotate 270 degree
            for(int j = rj; j >= lj; --j) {
                for(int i = li; i <= ri; ++i) {
                    if(grid[i][j] == 2) s4 += "1";
                    else s4 += "0";
                }
                s4 += "*";
            }
            if(rec.find(s4) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            
            string s5 = ""; // up/down reflection
            for(int i = ri; i >= li; --i) {
                for(int j = lj; j <= rj; ++j) {
                    if(grid[i][j] == 2) s5 += "1";
                    else s5 += "0";
                }
                s5 += "*";
            }
            if(rec.find(s5) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            
            string s6 = ""; // up/down reflection
            for(int j = rj; j >= lj; --j) {
                for(int i = ri; i >= li; --i) {
                    if(grid[i][j] == 2) s6 += "1";
                    else s6 += "0";
                }
                s6 += "*";
            }
            if(rec.find(s6) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            
            string s7 = ""; // left/right reflection
            for(int i = li; i <= ri; ++i) {
                for(int j = rj; j >= lj; --j) {
                    if(grid[i][j] == 2) s7 += "1";
                    else s7 += "0";
                }
                s7 += "*";
            }
            if(rec.find(s7) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            
            string s8 = ""; // left/right reflection
            for(int j = lj; j <= rj; ++j) {
                for(int i = li; i <= ri; ++i) {
                    if(grid[i][j] == 2) s8 += "1";
                    else s8 += "0";
                }
                s8 += "*";
            }
            if(rec.find(s8) != rec.end()) { restore(grid, li, lj, ri, rj); return false;}
            restore(grid, li, lj, ri, rj);
            rec.insert(s1);rec.insert(s2);rec.insert(s3);rec.insert(s4);
            rec.insert(s5);rec.insert(s6);rec.insert(s7);rec.insert(s8);
            return true;
        }
        
        void restore(vector<vector<int>>& grid, int li, int lj, int ri, int rj) {
            for(int j = lj; j <= rj; ++j) {
                for(int i = li; i <= ri; ++i) {
                    if(grid[i][j] == 2) grid[i][j] = 0;
                }
            }
        }
    };
    

Log in to reply
 

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