694.Number of Distinct Islands¶

694.Number of Distinct Islands¶

Tags: Medium Depth-first Search Hash Table

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

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 and only if one island can be translated (and not rotated or reflected) to equal the other.

Example 1:

Given the above grid map, return 1.

Example 2:

Given the above grid map, return 3.

Notice that:

11
1

and

 1
11

are considered different island shapes, because we do not consider reflection / rotation. Note: The length of each dimension in the given grid does not exceed 50.

很明显需要用DFS去搜索岛屿的数量，关键就是如何判断岛屿的形状，很自然的就联想到哈希，以第二个样例为例，右下角的平移到左上角，其实相当于右下角岛屿所有点的横纵坐标都减去这部分岛屿的最小横纵坐标，相当于归一化。

定义一个结构体Node存储横纵坐标，并用一个数组seq保存属于同一个岛屿的Node，当一个DFS结束，我们先进行归一化，也就是所有元素减去对应部分的最小横纵坐标，然后排序。

接下来就是如何去判断序列是否一样了，如果保存所有的Node，占据的空间大，而且比较起来很费时间，联想到1496判断路径是否相交的方法，可以把序列里的节点坐标看成一个字符序列，注意每个Node的横纵坐标用,分隔。利用字符串哈希的办法，这样就很节省存储空间，最后其实只需要知道unordered_set的大小即可。

class Solution {
    typedef unsigned long long ull;
    static constexpr ull base = 13331;
    unordered_set<ull> us;

    struct Node
    {
        int x, y;
        Node(int x, int y) : x(x), y(y) {}

        bool operator<(const Node & obj) const
        { return (x < obj.x) || (x == obj.x && y < obj.y); }
    };

    int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};


public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<Node> seq;
        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    seq.push_back(Node(i, j));
                    int minX = i, minY = j;
                    DFS(grid, seq, i, j, minX, minY);
                    Hash(seq, minX, minY);
                    seq.clear();
                }
            }
        }

        return us.size();
    }

    void DFS(vector<vector<int>>& grid, vector<Node> & seq, int row, int col, int & minX, int & minY)
    {
        int m = grid.size(), n = grid[0].size();
        grid[row][col] = 0;

        for (int i = 0; i < 4; ++i) {
            int nextRow = row + direction[i][0];
            int nextCol = col + direction[i][1];
            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && grid[nextRow][nextCol]) {
                seq.push_back(Node(nextRow, nextCol));
                minX = min(minX, nextRow), minY = min(minY, nextCol);
                DFS(grid, seq, nextRow, nextCol, minX, minY);
            }
        }
    }

    void Hash(vector<Node> & seq, const int & minX, const int & minY)
    {
        sort(seq.begin(), seq.end());
        for (auto & e : seq) { e.x -= minX, e.y -= minY; }

        ull res = 0;
        const ull square = base * base, triple = square * base;

        for (auto & e : seq) {
            res = res * triple + e.x * square + (ull)(',') * base + e.y;
        }

        us.emplace(res);
    }
};