参考自博客https://leetcode-cn.com/problems/island-perimeter/solution/tu-jie-jian-ji-er-qiao-miao-de-dfs-fang-fa-java-by/
如何在网格上做DFS
网格问题是这样的一类搜索问题：有mn个小方格，组成一个网络，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。这种题目乍一看可能有点麻烦，实际上思路非常明确，就是使用DFS搜索的方法。
*如何构造方格类DFS的代码结构**

  1. 首先要明白，每个方格与其上下左右的四个方格相邻，那么DFS每次就需要分出四个方向；
    //基本的DFS框架：每次搜索四个相邻方格
void dfs(vector<vector<int>> &grid,int row,int col)
{
 dfs(grid,row-1,col); //上边方格
 dfs(grid,row,col+1); //右边方格
 dfs(grid,row+1,col); //下边相邻
 dfs(grid,row,col-1); //左边相邻
}
    但是，对于网络边缘的方格，上下左右并不都有邻居。一种做法是在递归调用之前判断方格的位置，例如位于左边缘，则不访问其左邻居。但是这样会比较麻烦，可以使用“先污染后治理”的方法，先做递归调用，再在每个DFS函数的开头判断坐标是否合法，不合法的直接返回，同样地，还需要判断该方格是否有岛屿（也就是值是否为1），否则也需要返回。
    //处理方格位于网格边缘的情况
void dfs(vector<vector<int>> &grid,int row,int col)
{
 //若坐标不合法，直接返回
 if(row<0 || row>=grid.size() || col<0 || col>=grid[0].size())
     return;
 if(grid[row][col]!=1) //若该方格不是岛屿，直接返回
     return;
 dfs(grid,row-1,col); //上边方格
 dfs(grid,row,col+1); //右边方格
 dfs(grid,row+1,col); //下边相邻
 dfs(grid,row,col-1); //左边相邻
}
    但是这样还有一个小问题：DFS可能会不停地“兜圈子”，永远停不下来，如下图所示：
    图片说明 ![图片说明]
    那么我们就需要标记遍历过的方格，保证方格不进行重复遍历，遍历遍历过的方格并不需要使用额外的空间，只需要改变方格中存储的值就可以，比如值为0表示非岛屿（不可遍历），值为1表示岛屿（可遍历），使用2表示已经遍历过的岛屿。
    图片说明
    这样就得到了网络DFS遍历的框架代码：
    //标记已遍历过的岛屿，不做重复遍历
void dfs(vector<vector<int>> &grid,int row,int col)
{
 //若坐标不合法，直接返回
 if(row<0 || row>=grid.size() || col<0 || col>=grid[0].size())
     return;
 //已遍历过（值为2）的岛屿在这里会直接返回，不会重复遍历
 if(grid[row][col]!=1) //若该方格不是岛屿，直接返回
     return;
 grid[row][col]=2; //将方格标记为“已遍历”
 dfs(grid,row-1,col); //上边方格
 dfs(grid,row,col+1); //右边方格
 dfs(grid,row+1,col); //下边相邻
 dfs(grid,row,col-1); //左边相邻
}

典序例题1——岛屿的周长
题目描述：给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
图片说明
岛屿的周长就是岛屿方格与非岛屿方格（也就是水域方格和网格的边缘）相邻的边的数量。将这个“相邻关系”对应到DFS遍历中，就是每当在DFS遍历中，从一个岛屿方格走向一个非岛屿方格就将周长加1.

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int islandPerimeter(vector<vector<int>>& grid) 
{
    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]==1) //题目当中说明只有一个岛屿，遍历一次dfs即可
                return dfs(grid,i,j,m,n);
        }
    }
    return 0;
}
int dfs(vector<vector<int>> &grid,int x,int y,int m,int n)
{
    //从一个岛屿方格走向网格边缘，周长加1
    if(x<0 || x>=m || y<0 || y>=n)
        return 1;
    //从一个岛屿方格走向水域方格，周长加1
    if(grid[x][y]==0) 
        return 1;
    if(grid[x][y]==2) //周围的方格已经访问过来，直接返回0
        return 0;
    grid[x][y]=2; //置该单元方格标记为“已遍历”
    int ans=0;
    for(int k=0;k<4;++k)
    {
        int tx=x+dx[k];
        int ty=y+dy[k];
        ans+=dfs(grid,tx,ty,m,n);
    }
    return ans;
}

典型例题二————岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
图片说明
分析：该题问的是岛屿的数量，那么首先要搞清楚岛屿是指什么？岛屿就是陆地通过横向或者纵向连接在一起构成的一大块陆地，这样由上面那道题的思路，我们就可以采用dfs算法对陆地的小方格进行遍历，每调用一次dfs就可以遍历该小方格所在的岛屿的全部方格，因此需要调用几次dfs函数就会有多少个岛屿存在了。

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int islandPerimeter(vector<vector<int>>& grid) 
{
    int m=grid.size(),n=grid[0].size(),count=0;
    for(int i=0;i<m;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(grid[i][j]==1) //题目当中说明只有一个岛屿，遍历一次dfs即可
            {
                dfs(grid,i,j,m,n);
                ++count;
            }
        }
    }
    return count;
}
void dfs(vector<vector<int>> &grid,int x,int y,int m,int n)
{
    if(x<0 || x>=m || y<0 || y>=n)
        return;
    if(grid[x][y]=='0') 
        return;
    if(grid[x][y]=='2')
        return;
    grid[x][y]='2'; //置该单元方格标记为“已遍历”
    for(int k=0;k<4;++k)
    {
        int tx=x+dx[k];
        int ty=y+dy[k];
        dfs(grid,tx,ty,m,n);
    }
}

典型例题三————最大岛屿面积
分析：要求最大岛屿面积，我们可以找出所有岛屿面积，取出其中最大值。那么怎样找出某一岛屿的面积呢？可以按照如下思路进行：1.从某位置出发，向四个方向探寻相连的陆地；2.每探寻到一块土地，计数加1；3.确保每块土地只会被探寻一次。这刚好就是图的一个遍历的过程，可以使用DFS算法来探寻相连的陆地。

int maxAreaOfIsland(vector<vector<int>>& grid) 
{
    int maxArea=0x80000000,curArea=0;
    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]==1)
            {
                curArea=0;
                dfs(grid,i,j,m,n,curArea);
                maxArea=max(maxArea,curArea);
            }
        }
    }
    return maxArea==0x80000000?0:maxArea;
}
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(vector<vector<int>> &grid,int x,int y,int m,int n,int &curArea)
{
    if(x<0 || x>=m || y<0 || y>=n || grid[x][y]==0)
        return;
    if(grid[x][y]==2)
        return;
    grid[x][y]=2;
    ++curArea;
    for(int k=0;k<4;++k)
    {
        int tx=x+dx[k];
        int ty=y+dy[k];
        dfs(grid,tx,ty,m,n,curArea);
    }
}