[LEETCODE][694. Number of Distinct Islands]

题目描述

694. 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:

11000 11000 00011 00011

Given the above grid map, return 1.

Example 2:

11011 10000 00001 11011

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.

分析

//小岛问题的话一般考虑进行上色，那么现在多了一个限定条件，如果可以转换的，算作一个
//那么现在关键变成，如何进行相同岛屿的判断
//用一个set来记录当前访问过的岛屿，并且岛屿的形状用一个string来表示，两者限定唯一性
//这个string，我们考虑用坐标来表示，假设当前的源点坐标为x0,y0
//以这个作为参考，每个点到当前源点两个坐标都进行记录，最终形成的岛屿序列我们作为当前岛屿标志

 

//dfs
class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        if(!grid.size() || !grid[0].size())
            return 0;
        unordered_set<string> myset;
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                if(grid[i][j]){
                    string repre; //当前岛屿的标志
                    dfs(grid,i,j,i,j,repre);
                    myset.insert(repre);
                }
            }
        }
        return myset.size();
    }
private:
    void dfs(vector<vector<int>>& grid,int x,int y,int tarx,int tary,string& s){
        if(!isValid(grid,x,y))
            return;
        if(grid[x][y]==0)
            return;
        grid[x][y]=0; //当前点标记为已访问
        s+=to_string(x-tarx)+to_string(y-tary);
        dfs(grid,x-1,y,tarx,tary,s);
        dfs(grid,x+1,y,tarx,tary,s);
        dfs(grid,x,y-1,tarx,tary,s);
        dfs(grid,x,y+1,tarx,tary,s);
    }
    bool isValid(vector<vector<int>>& grid,int x,int y){
        if(x<0||x>=grid.size()||y<0||y>=grid[0].size())
            return false;
        return true;
    }
};

//bfs的写法
class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        if(!grid.size() || !grid[0].size())
            return 0;
        int m=grid.size(),n=grid[0].size();
        vector<int> offsets= {0, 1, 0, -1, 0}; //方向数组，用于四个方向上的扩展
        unordered_set<string> islands;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    grid[i][j] = 0;
                    string island;
                    queue<pair<int,int>> todo; //周围相连的，值为1的所有点的坐标
                    todo.push({i, j});
                    while (!todo.empty()) {
                        pair<int,int> p = todo.front();
                        todo.pop();
                        for (int k = 0; k < 4; k++) {
                            int r = p.first + offsets[k], c = p.second + offsets[k + 1]; //下一个点的坐标
                            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c]) {
                                grid[r][c] = 0;
                                todo.push({r, c});
                                island += to_string(r - i) + to_string(c - j); //记录对应的string
                            }
                        }
                    }
                    islands.insert(island);
                }
            }
        }
        return islands.size();
    }
};

总结 

基础的bfs和dfs是好写的，关键是一些特殊的题目，如何进行唯一性的标识，可能是上色，可能是string标识，需要多总结