> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/graph-search/bfsdfs/number-of-distinct-islands-ii.md).

# 711. Number of Distinct Islands II

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 the **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.

**Thoughts:**

DFS + sorting: first use DFS to group all the islands, and then for "normalize" each group by listing all the possible

cases of index presentation of a island and pick the canonical one.

**Code**

```cpp
class Solution {
    // typedef pair<int,int> point; old fashion :(
    using point = pair<int,int>; // new fashion :)
    using points = vector<point>;
    map<int, points> m;
public:
    int numDistinctIslands2(vector<vector<int>>& grid) {
        set <points> distinct; 
        if(grid.size()==0) return distinct.size();        
        // step1: find island
        int count = 1;
        for(int i = 0; i < grid.size(); i++)
            for(int j =0; j < grid[i].size(); j++)if(grid[i][j] == 1){
                    dfs(i,j,grid,++count);
                    distinct.insert(norm(m[count]));
                }
        return distinct.size();
    }

    void dfs(int r, int c, vector<vector<int>>&grid, int cnt){
        if (r < 0  || r >= grid.size() || c < 0 || c >= grid[0].size()) return;
        if(grid[r][c] != 1) return; // must be 1 since other number means "unpassable"
        grid[r][c] = cnt; // "infection" , "propogation"
        m[cnt].emplace_back(r,c);// record
        dfs(r + 1, c , grid, cnt); //down
        dfs(r - 1, c , grid, cnt); //up
        dfs(r , c + 1 , grid, cnt); //right
        dfs(r , c - 1, grid, cnt); //left
    }

    points norm(points v){
        // expand all the possibilities of a norm
        vector<points> spand(8);
        for(auto p: v){
            int x = p.first, y = p.second;
            // 8 cases
            spand[0].emplace_back(x , y);            
            spand[1].emplace_back(x , -y); // reflextion by vertical
            spand[2].emplace_back(-x , y); // reflextion by horizontal
            spand[3].emplace_back(-x , -y); // reflextion by (0,0)
            spand[4].emplace_back(y , -x); // rotation by 90 clockwise
            spand[5].emplace_back(-y , x); // rotation by 90 counter-clockwise
            spand[6].emplace_back(-y , -x); // rotation by 90 counter-clockwise + reflectin by vertical 
                                            // or rotation by 90 clockwise + reflection by horizontal
            spand[7].emplace_back(y , x);   // rotation by 90 clockwise + refletion by vertical 
                                            // rotation by 90 counter-clockwise + reflection by horizontal
        }

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

        // normalization: fix the offset as (0,0)
        for (auto &l:spand) {
            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};
        }

        // finally sort the spand to get the canical representation
        sort(spand.begin(), spand.end());
        return spand[0];
    }

};
```