【深度优先搜索】岛屿的周长

463. 岛屿的周长

如果陆地有4个邻接陆地，那么这个陆地周长算为0

如果陆地有3个邻接陆地，那么这个陆地周长算1

如果陆地有2个邻接陆地，那么这个陆地周长算2

如果陆地有1个邻接陆地，那么这个陆地周长算3

如果陆地没有邻接陆地，那么这个路径周长算4

因为只有一个连通块，所以只需要一次dfs就可以访问完所有的陆地。

在访问一个陆地时，加上它算的周长，然后递归访问它的邻边

注意，vis判断去重，否则会无限循环。

注意:res需要定义为全局变量，否则会出错。

class Solution {
public:
    vector<vector<int>>G;
    int n, m;
    bool vis[105][105];
    int res=0;
    void dfs(int x, int y) {
        if (!(x >= 0 && y >= 0 && x < n && y < m))return;
        if (G[x][y]==0)return;
        if (vis[x][y])return;
        int cnt = 0;
        vis[x][y] = true;
        if (x - 1 >= 0 && G[x - 1][y] == 1)cnt++;
        if (x + 1 < n && G[x + 1][y] == 1)cnt++;
        if (y - 1 >= 0 && G[x][y - 1] == 1)cnt++;
        if (y + 1 < m && G[x][y + 1] == 1)cnt++;
        res+=4-cnt;
        dfs(x + 1, y);
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        G = grid;
        n = grid.size();
        m = grid[0].size();
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (G[i][j] == 1) {
                    dfs(i,j);
                    break;
                }
            }
        }
        return res;
    }
};