0463. Island Perimeter ====================== 题目信息 -------- :题号: 0463 :难度: Easy :主题: 二值网格、单一岛屿、四邻接、外露边长 :原题: `LeetCode 0463 `_ :重点: 陆地格边长为 1、共享边不计周长、网格外和水格构成边界、岛内没有湖泊 题目重述 -------- 给定只包含 0 和 1 的矩阵 ``grid``,1 表示陆地,0 表示水。网格中恰好有一个由上下左右相邻陆地格组成的岛屿,并且岛屿内部没有完全被陆地包围的湖泊。返回该岛屿的周长。 每个格子是边长为 1 的正方形。陆地格与水格或网格外部相邻的一条边贡献 1 个单位周长;两个陆地格共享的边位于岛屿内部,不计入周长。矩阵行列数位于 ``[1, 100]``。 自建示例 -------- 三个格子组成 L 形: .. code-block:: text 输入:grid = [[1,1],[1,0]] 输出:8 解释:三个陆地格单独共有 12 条边,其中两对相邻陆地共享 2 条边,每条共享边会从外周长中消去两侧,因此周长为 12 - 4 = 8。 单个陆地格: .. code-block:: text 输入:grid = [[1]] 输出:4 解释:该格子的四条边都面向网格外部。 从每块陆地的四条边累计 ---------------------- 一块陆地初始贡献 4 条边。若它的上方或左方也是陆地,则这条共享边已经在之前或当前的计数中出现两次,减去 2;只检查上、左两个方向,就能在不重复计算的前提下处理所有相邻陆地对。面向网格外或水的边不会触发扣除,自然保留在周长中。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int islandPerimeter(std::vector>& grid) { int rows = static_cast(grid.size()); int columns = static_cast(grid[0].size()); int perimeter = 0; for (int row = 0; row < rows; ++row) { for (int column = 0; column < columns; ++column) { if (grid[row][column] == 0) continue; perimeter += 4; if (row > 0 && grid[row - 1][column] == 1) { perimeter -= 2; } if (column > 0 && grid[row][column - 1] == 1) { perimeter -= 2; } } } return perimeter; } }; 代码分析 -------- 每个陆地格与相邻陆地共享的边会从两块格子的独立边数中消失,因此每发现一对相邻陆地扣除 2;只从上、左检查保证每对只处理一次。遍历每个格子一次,时间复杂度为 ``O(rows * columns)``,额外空间复杂度为 ``O(1)``。