每日一题：每天一个新挑战；
循序渐进：从易到难，扎实掌握；
系统分类：按数据结构分类，有助于构建知识框架；
丰富题量：100 道精选题，覆盖简单/中等/困难难度。

给定一个 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

代码卡片

题目解析

题目要求我们计算给定的二维网格中岛屿的周长。岛屿由值为 1 的格子组成，而水域则由值为 0 的格子表示。格子只能在水平方向或垂直方向相连，不能在对角线方向相连。题目保证只有一个岛屿，并且该岛屿没有湖泊。我们需要计算出该岛屿的周长。

方法一：逐步读取

我们可以通过遍历整个网格来计算岛屿的周长。每当遇到一个值为 1 的格子时，它的初始周长为 4，但如果它与其他陆地格子相邻（即上下左右相邻），每个相邻的方向会减少 1 的周长。这样，我们就可以通过计算所有 1 的格子的周长来得出整个岛屿的周长。

时间复杂度：O(row * col)。我们需要遍历整个网格的所有格子来计算周长，因此时间复杂度是网格的大小。
空间复杂度：O(1)。我们只需要一个额外的变量来存储周长，因此空间复杂度是常数级别的。

var islandPerimeter = function (grid) {
    let perimeter = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 1) {
                perimeter += 4;
                if (i > 0 && grid[i - 1][j] === 1) perimeter -= 2;
                if (j > 0 && grid[i][j - 1] === 1) perimeter -= 2;
            }
        }
    }
    return perimeter;
}

方法二：提前停止

我们可以在计算周长的同时，尽量减少不必要的遍历。一旦我们遇到一个陆地格子，我们就立即计算它的周长，而不再继续遍历与之相连的陆地格子。这样可以在一定程度上减少不必要的计算，尤其是在大型网格中。

时间复杂度：O(row _ col)。在最坏情况下，我们可能需要遍历整个网格中的所有格子，这与方法一的时间复杂度相同。因此时间复杂度为 O(row _ col)。
空间复杂度：O(row _ col)。在最坏情况下，递归栈的深度可能会达到整个网格的大小，特别是当岛屿占据了大部分网格时。因此空间复杂度为 O(row _ col)。

var islandPerimeter = function (grid) {
    let perimeter = 0;
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === 0) {
            return 1;
        }
        if (grid[i][j] === -1) {
            return 0;
        }

        grid[i][j] = -1;
        let localPerimeter = 0;

        for (const [di, dj] of directions) {
            localPerimeter += dfs(i + di, j + dj);
        }

        return localPerimeter;
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 1) {
                perimeter = dfs(i, j);
                return perimeter;
            }
        }
    }

    return perimeter;
}