参考：
岛屿类问题的通用解法、DFS 遍历框架

一、网格类问题DFS框架

网格 DFS 遍历的框架代码：

void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    // 如果坐标 (r, c) 超出了网格范围，直接返回
    if (!inArea(grid, r, c)) {
        return;
    }
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
            && 0 <= c && c < grid[0].length;
}

如何避免重复遍历
网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。这是因为，网格结构本质上是一个「图」，我们可以把每个格子看成图中的结点，每个结点有向上下左右的四条边。在图中遍历时，自然可能遇到重复遍历结点。
如何避免这样的重复遍历呢？答案是标记已经遍历过的格子。以岛屿问题为例，我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。也就是说，每个格子可能取三个值：

  • 0 —— 海洋格子
  • 1 —— 陆地格子（未遍历过）
  • 2 —— 陆地格子（已遍历过） 
void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    // 如果这个格子不是岛屿，直接返回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 将格子标记为「已遍历过」

    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
            && 0 <= c && c < grid[0].length;
}

二、解题

1、岛屿数量

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

关键在于： 在进行遍历时，统计了该点处的岛屿后，处理掉其他的岛屿

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    void dfs(vector<vector<char>>& grid, int r, int c)
    {
        if(!inArea(grid, r, c)) return ;

        if(grid[r][c] != '1') return;

        grid[r][c] = '2';

        dfs(grid, r-1, c);
        dfs(grid, r, c-1);
        dfs(grid, r+1, c);
        dfs(grid, r, c+1);
    }

    bool inArea(vector<vector<char>>& grid, int r, int c)
    {
        if(r>=0 && r <grid.size() && c >= 0 && c < grid[0].size()) return true;
        else return false;
    }


    int solve(vector<vector<char> >& grid) {
        // write code here
        int n = grid.size();
        int m = grid[0].size();
        int res = 0;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(grid[i][j] == '1')
                {
                    res+=1;
                    dfs(grid, i, j);
                }
            }
        }

        return res;
    }

};

2、岛屿周长

岛屿的周长是计算岛屿全部的「边缘」，而这些边缘就是我们在 DFS 遍历中，dfs 函数返回的位置。观察题目示例，我们可以将岛屿的周长中的边分为两类，如下图所示。黄色的边是与网格边界相邻的周长，而蓝色的边是与海洋格子相邻的周长。

图片说明

当我们的 dfs 函数因为「坐标 (r, c) 超出网格范围」返回的时候，实际上就经过了一条黄色的边；而当函数因为「当前格子是海洋格子」返回的时候，实际上就经过了一条蓝色的边。这样，我们就把岛屿的周长跟 DFS 遍历联系起来了，

class Solution {
public:

    int dfs(vector<vector<int>>& grid, int r, int c)
    {
        if(!inArea(grid,r,c)) return 1;

        if(grid[r][c] == 0) return 1;

        if(grid[r][c] == 2) return 0; //已经遍历过的格子

        grid[r][c] = 2;

        return dfs(grid, r-1, c) + dfs(grid, r, c-1) + dfs(grid, r+1, c) + dfs(grid, r, c+1);
    }


    bool inArea(vector<vector<int>>& grid, int r, int c)
    {
        return r>=0 && r<grid.size() && c>=0 && c<grid[0].size();
    }


    int islandPerimeter(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int res = 0;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(grid[i][j] == 1) res += dfs(grid,i,j);
            }
        }
        return res;
    }
};

3、岛屿的最大面积

class Solution {
public:
    bool inArea(vector<vector<int>>& grid, int r, int c)
    {
        return r>=0 && r<grid.size() && c>=0 && c < grid[0].size();
    }

    int dfs(vector<vector<int>>& grid, int r, int c)
    {
        if(!inArea(grid, r, c)) return 0;

        if(grid[r][c] != 1)  return 0;

        grid[r][c] = 2;

        return 1 + dfs(grid, r-1, c) + dfs(grid, r, c-1) + dfs(grid, r+1, c) + dfs(grid, r, c+1);
    }


    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int res = 0;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(grid[i][j] == 1)
                {
                    int temp = dfs(grid, i, j);
                    res = max(res, temp);
                }
            }
        }
        return res;
    }
};

4、人造岛的最大面积

两次遍历

class Solution {
public:
    bool inArea(vector<vector<int>>& grid, int r, int c)
    {
        return r>=0 && r<grid.size() && c>=0 && c < grid[0].size();
    }

    int area(vector<vector<int>>& grid, int r, int c, int index)
    {
        if(!inArea(grid, r, c)) return 0;

        if(grid[r][c] != 1)  return 0;

        grid[r][c] = index;

        return 1 + area(grid, r-1, c, index) + area(grid, r, c-1, index) + area(grid, r+1, c, index) + area(grid, r, c+1, index);
    }
    /**
     * 对于海洋格子，找到上下左右
     * 每个方向，都要确保有效inArea以及是陆地格子，则表示是该海洋格子的陆地邻居
     */
    set<int> findneibor(vector<vector<int>>& grid, int r, int c)
    {
        set<int> tmp;
        if (inArea(grid,r-1,c) && grid[r-1][c] != 0){
            tmp.insert(grid[r-1][c]);
        }
        if (inArea(grid,r+1,c) && grid[r+1][c] != 0){
            tmp.insert(grid[r+1][c]);
        }
        if (inArea(grid,r,c-1) && grid[r][c-1] != 0){
            tmp.insert(grid[r][c-1]);
        }
        if (inArea(grid,r,c+1) && grid[r][c+1] != 0){
            tmp.insert(grid[r][c+1]);
        }
        return tmp;

    }


    int largestIsland(vector<vector<int>>& grid) {
        int res = 0;
        int index = 2;
        map<int, int> mp; //岛屿编号， 岛屿面积

        //第一遍遍历 记录岛屿大小
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[0].size(); j++)
            {
                if(grid[i][j] == 1)
                {
                    int Area = area(grid, i, j, index);
                    mp.insert({index, Area});
                    index++;
                    res = max(res, Area);
                }
            }
        }

        if(res == 0) return 1;

        //第二遍遍历，遍历海洋格子，假设这个格子填充，那么就把上下左右是陆地的格子所在的岛屿连接起来
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[0].size(); j++)
            {
                if(grid[i][j] == 0)
                {
                    set<int> st = findneibor(grid,i,j);//把上下左右邻居放入set去重
                    if(st.size() < 1) continue;//如果海洋格子周围没有格子不必计算
                    int twoIsland = 1;//填充这个格子，初始为1，这个变量记录合并岛屿后的面积
                    for(set<int>::iterator it=st.begin() ; it!=st.end(); it++)
                    {
                        twoIsland = twoIsland + mp[*it];
                    }
                    res = max(res, twoIsland);
                }
            }
        }
        return res;
    }
};

5、不同岛屿的数量

class Solution {
public:
    vector<int> res;
    int numDistinctIslands(vector<vector<int>>& grid) {
        if(grid.size()==0){
            return 0;
        }
        set<vector<pair<int,int>>> gridlength;
        vector<vector<int>> visited(grid.size(),vector<int>(grid[0].size()));
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                if(grid[i][j]==1&&visited[i][j]==0){
                    caclu(grid,visited,i,j);
                    sort(res.begin(),res.end());
                    int minrow=grid.si***column=grid[0].size();  //每块陆地的最小行号，最小列号
                    for(auto &item:res){
                        minrow=min(int(item/(grid[0].si***row); // 更新每块陆地的最小行号，最小列号
                        mincolumn=min(int(item%(grid[0].si***column);
                    }
                    vector<pair<int,int>> temp;
                    for(auto &item:res){
                        int row=item/(grid[0].si***row;   // 计算平移后的位置
                        int column=item%(grid[0].si***column;
                        temp.push_back(move(pair<int,int>(row,column)));
                    }
                    gridlength.insert(move(temp));
                }
                // else{
                //     //已被计算为岛屿
                //     continue;
                // }
            }
        }

        return gridlength.size();
    }
    void caclu(const vector<vector<int>> &grid,vector<vector<int>> &visited,const int &i,const int &j){
        res.clear();
        dfs(grid,visited,i,j);
    }
    void dfs(const vector<vector<int>> &grid,vector<vector<int>> &visited,const int &i,const int &j){
        if(i<0||j<0||i>=grid.size()||j>=grid[0].size()||visited[i][j]||grid[i][j]==0){
            return;
        }
        visited[i][j]=1;
        res.push_back(i*grid[0].size()+j); // 岛屿空间 在 grid中的编号
        dfs(grid,visited,i+1,j);
        dfs(grid,visited,i-1,j);
        dfs(grid,visited,i,j+1);
        dfs(grid,visited,i,j-1);
    }
};
/*
作者：ZZZZHZZZZ
链接：https://leetcode-cn.com/problems/number-of-distinct-islands/solution/694bu-tong-dao-yu-de-shu-liang-by-zzzzhz-cnyy/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/