Leetcode.463 岛屿的周长

题目链接

Leetcode.463 岛屿的周长 easy

题目描述

给定一个 row x col的二维网格地图 grid，其中：grid[i][j] = 1表示陆地， grid[i][j] = 0表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

输入：grid = [[1]]
输出：4

示例 3：

输入：grid = [[1,0]]
输出：4

提示：

• $row==grid.length$
• $col==grid[i].length$
• $1<=row,col<=100$
• grid[i][j]为 0 或 1

解法：dfs

我们发现这个岛屿的周长实际上就是：由陆地走向水域的次数 + 由陆地走向边界的次数。

将访问过的陆地标记为 2代表已经访问过。

时间复杂度： $O(m\ast n)$

C++代码：

class Solution {
public:
    int m,n;

    int dfs(int i ,int j,vector<vector<int>>& g){
        //遇到边界 周长也要 +1
        if(i < 0 || i >= m || j < 0 || j >= n) return 1;
        
        //由陆地 走向 水域 ，周长+1
        if(g[i][j] == 0) return 1;

        //已经访问过的陆地 直接返回 0
        if(g[i][j] == 2) return 0;

        //将当前陆地 标记为访问过
        g[i][j] = 2;

        return dfs(i-1,j,g) + dfs(i+1,j,g) + dfs(i,j-1,g) + dfs(i,j+1,g);
    }

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

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

        return -1;
    }
};