[LeetCode] 711. Number of Distinct Islands II

[grandyang]

 

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if they have the same shape, or have the same shape after rotation (90, 180, or 270 degrees only) or reflection (left/right direction or up/down direction).

Example 1:

11000
10000
00001
00011

Given the above grid map, return 1. 

Notice that:

11
1

and

 1
11

are considered same island shapes. Because if we make a 180 degrees clockwise rotation on the first island, then two islands will have the same shapes.

 

Example 2:

11100
10001
01001
01110

Given the above grid map, return 2.

Here are the two distinct islands:

111
1

and

1
1

Notice that:

111
1

and

1
111

are considered same island shapes. Because if we flip the first array in the up/down direction, then they have the same shapes.

 

Note: The length of each dimension in the given grid does not exceed 50.

 

这道题是之前那道 Number of Distinct Islands 的拓展，之前那道题定义的相同的岛屿必须是形状完全相同的，而这里岛屿则可以进行 90 度旋转，或者是水平竖直方向的镜面对称，这样就极大的增加了难度，因为在判断两个形状是否属于一个岛屿的时候，要考虑各种各样的情况，十分的复杂。这道题最大的难点也就是在于如何对同一种岛屿形状进行建模，使得其所有翻转或者对称的岛屿形状可以归属到同一类中。在之前那道 Number of Distinct Islands 中，由于是有平移操作，使用的 trick 是利用相对位移保持不变的特性来确定同一种同一种岛屿形状的，在这道题中显然不适用了，因为这里各种变换会破坏相对位移。那该怎么办呢？比如现在有几个长度相同的数组，是乱序的，怎么才能知道这些数组是否可以通过排序变成相同的数组，则最简单的方法就是对所有的数组进行排序，排序后若相同，则表示属于同一类，那么这个排序后的数组其实就可以代表所有同一种数组。借鉴这种思路，其实要做的就是找到一种建模方式，将所有属于同一类的岛屿形状都转为其唯一的结构，然后放到一个有去处重复功能的集合中，最后集合中元素的个数即为不同岛屿的个数。

大体思路有了，再来看具体该如何实施。首先还是要找出每个单独的小岛，即找出所有相连的1，这跟之前的题目的做法相同，可以使用 DFS 或者 BFS 来找，这里先使用 DFS 来做。方法是遍历 grid 数组，当遇到为1的位置，说明遇到小岛了，对该位置调用递归函数，将和其相连的所有位置都存入到 shape 数组中。递归数组结束后，就有了该小岛所有位置的坐标，现在就要对其进行转换，或者叫 normalize，目的是变换成同一种岛屿形状的唯一表示。对于每一个坐标位置，其实总共有8种变换可能，x和y都可以分别变为相反数，且也可以同时变为相反数，再加上其本身，这就4种了。同时，上面的每一种情况都可以交换x和y的位置，这样总共就有8中变换方法，每一种情况都要考虑，所以使用8个大小相同的数组来保存各自所有的点。对于每一种形状，都对其所有的点进行排序，然后将每个点的绝对坐标变为相对坐标，即每个点都减去排序后第一个点的坐标，最后再对这8个形状排个序。这样一顿操作猛如虎之后，只要是属于同一个岛屿的形状，最后都会得到一模一样的8个形状数组，为了简单起见，只选取第一个形状形状当作这同一种岛屿的模型代表，并将其加入那个可以去重复的集合中即可，参见代码如下：

 

解法一：

class Solution {
public:
    int numDistinctIslands2(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        set<vector<pair<int, int>>> st;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    vector<pair<int, int>> shape;
                    helper(grid, i, j, shape);
                    st.insert(normalize(shape));
                }
            }
        }
        return st.size();
    }
    void helper(vector<vector<int>>& grid, int x, int y, vector<pair<int, int>>& shape) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) return;
        if (grid[x][y] == 0) return;
        grid[x][y] = 0;
        shape.push_back({x, y});
        helper(grid, x + 1, y, shape);
        helper(grid, x - 1, y, shape);
        helper(grid, x, y + 1, shape);
        helper(grid, x, y - 1, shape);
    }
    vector<pair<int, int>> normalize(vector<pair<int, int>>& shape) {
        vector<vector<pair<int, int>>> shapes(8);
        for (auto &a : shape) {
            int x = a.first, y = a.second;
            shapes[0].push_back({x, y});
            shapes[1].push_back({x, -y});
            shapes[2].push_back({-x, y});
            shapes[3].push_back({-x, -y});
            shapes[4].push_back({y, x});
            shapes[5].push_back({y, -x});
            shapes[6].push_back({-y, x});
            shapes[7].push_back({-y, -x});
        }
        for (auto &a : shapes) {
            sort(a.begin(), a.end());
            for (int i = (int)shape.size() - 1; i >= 0; --i) {
                a[i].first -= a[0].first;
                a[i].second -= a[0].second;
            }
        }
        sort(shapes.begin(), shapes.end());
        return shapes[0];
    }
};

 

下面这种写法是 BFS 形式的，大体思路相同，就是在找每个岛屿的时候使用的是迭代的写法，找出了每个岛屿位置集合 shape 之后，进行 normalize 操作跟上面完全相同，最后还是看去重复集合中元素的个数即可，参见代码如下：

 

解法二：

class Solution {
public:
    int numDistinctIslands2(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        set<vector<pair<int, int>>> st;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) continue;
                grid[i][j] = 0;
                vector<pair<int, int>> shape{{i, j}};
                int i = 0;
                while (i < shape.size()) {
                    auto t = shape[i++];
                    int x = t.first, y = t.second;
                    if (x > 0 && grid[x - 1][y] != 0) {
                        grid[x - 1][y] = 0;
                        shape.push_back({x - 1, y});
                    }
                    if (x + 1 < m && grid[x + 1][y] != 0) {
                        grid[x + 1][y] = 0;
                        shape.push_back({x + 1, y});
                    }
                    if (y > 0 && grid[x][y - 1] != 0) {
                        grid[x][y - 1] = 0;
                        shape.push_back({x, y - 1});
                    }
                    if (y + 1 < n && grid[x][y + 1] != 0) {
                        grid[x][y + 1] = 0;
                        shape.push_back({x, y + 1});
                    }
                }
                st.insert(normalize(shape));
            }
        }
        return st.size();
    }
    vector<pair<int, int>> normalize(vector<pair<int, int>>& shape) {
        vector<vector<pair<int, int>>> shapes(8);
        for (auto &a : shape) {
            int x = a.first, y = a.second;
            shapes[0].push_back({x, y});
            shapes[1].push_back({x, -y});
            shapes[2].push_back({-x, y});
            shapes[3].push_back({-x, -y});
            shapes[4].push_back({y, x});
            shapes[5].push_back({y, -x});
            shapes[6].push_back({-y, x});
            shapes[7].push_back({-y, -x});
        }
        for (auto &a : shapes) {
            sort(a.begin(), a.end());
            for (int i = (int)shape.size() - 1; i >= 0; --i) {
                a[i].first -= a[0].first;
                a[i].second -= a[0].second;
            }
        }
        sort(shapes.begin(), shapes.end());
        return shapes[0];
    }
};

 

Github 同步地址：

#711

 

类似题目：

Number of Distinct Islands

 

参考资料：

https://leetcode.com/problems/number-of-distinct-islands-ii/

https://leetcode.com/problems/number-of-distinct-islands-ii/discuss/231300/C%2B%2B-BFSDFS

https://leetcode.com/problems/number-of-distinct-islands-ii/discuss/108794/Consise-C%2B%2B-solution-using-DFS-%2Bsorting-to-find-canonical-representation-for-each-island

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[laoxihongshi]

这里有个解法：http://storypku.com/2017/10/leetcode-question-711-number-of-distinct-islands-ii/
判断形状相同的方式真的看不懂：

class Solution {
public:
    int numDistinctIslands2(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        if (n == 0) return 0;
        
        std::unordered_set<int> signatures;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c]) {
                    vector<pair<int, int>> pts;
                    visit(grid, m, n, r, c, pts);
                    int hash = compute_hash(pts);
                    signatures.insert(hash);
                }
            }
        }
        
        return signatures.size();
    }
    
private:
    int compute_hash(vector<pair<int, int>>& pts) {
        int n = pts.size();
        int hash = 0;
        int xmin = INT_MAX, ymin = INT_MAX, xmax = INT_MIN, ymax = INT_MIN;
        for (int i = 0; i < n; ++i) {
            const auto& pt1 = pts[i];
            xmin = std::min(xmin, pt1.first);
            ymin = std::min(ymin, pt1.second);
            xmax = std::max(xmax, pt1.first);
            ymax = std::max(ymax, pt1.second);
            for (int j = i + 1; j < n; ++j) {
                const auto& pt2 = pts[j];
                int delta_x = pt1.first - pt2.first;
                int delta_y = pt1.second - pt2.second;
                if (delta_x == 0 || delta_y == 0) {
                    hash += 19 * (delta_x * delta_x + delta_y * delta_y);
                } else {
                    hash += 31 * (delta_x * delta_x + delta_y * delta_y);
                }
                
            }
        }
        
        int delta_x = xmax - xmin, delta_y = ymax - ymin;
        hash += 193 * (delta_x * delta_x + delta_y * delta_y) + 97 * delta_x * delta_y;
        return hash;
    }
    
    void visit(vector<vector<int>>& grid, int m, int n, int r, int c,
               vector<pair<int, int>>& pts) {
        bool outOfBound = (r < 0 || r >= m || c < 0 || c >= n);
        if (outOfBound || grid[r][c] == 0) return;
        
        grid[r][c] = 0;
        pts.emplace_back(r, c);
        visit(grid, m, n, r - 1, c, pts);
        visit(grid, m, n, r + 1, c, pts);
        visit(grid, m, n, r, c - 1, pts);
        visit(grid, m, n, r, c + 1, pts);
    }    
};```

[grandyang]

已添加讲解～