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
  • grid 中有且仅有一个岛屿

解题思路

这道题有两种主要的解法思路：

方法一：直接计算（推荐） 对于每个陆地格子，我们检查它的四个方向（上下左右）。如果某个方向是边界或者是水域，那么这个方向就贡献一条边到周长。具体来说，一个陆地格子的周长贡献为：4 - 相邻陆地格子的数量。

方法二：DFS/BFS遍历 从任意一个陆地格子开始，使用深度优先搜索或广度优先搜索遍历整个岛屿，在遍历过程中计算周长。

推荐使用方法一，因为它实现简单、时间复杂度低，且不需要额外的空间来标记访问过的格子。

算法步骤：

  1. 遍历整个网格
  2. 对于每个陆地格子，检查其四个相邻位置
  3. 如果相邻位置是边界外或者是水域，则周长加1
  4. 返回总周长

这种方法的优势是代码简洁，逻辑清晰，且效率很高。

代码实现

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        int perimeter = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    // 检查上方
                    if (i == 0 || grid[i-1][j] == 0) {
                        perimeter++;
                    }
                    // 检查下方
                    if (i == rows-1 || grid[i+1][j] == 0) {
                        perimeter++;
                    }
                    // 检查左方
                    if (j == 0 || grid[i][j-1] == 0) {
                        perimeter++;
                    }
                    // 检查右方
                    if (j == cols-1 || grid[i][j+1] == 0) {
                        perimeter++;
                    }
                }
            }
        }
        
        return perimeter;
    }
};

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        perimeter = 0
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    # 检查上方
                    if i == 0 or grid[i-1][j] == 0:
                        perimeter += 1
                    # 检查下方
                    if i == rows-1 or grid[i+1][j] == 0:
                        perimeter += 1
                    # 检查左方
                    if j == 0 or grid[i][j-1] == 0:
                        perimeter += 1
                    # 检查右方
                    if j == cols-1 or grid[i][j+1] == 0:
                        perimeter += 1
        
        return perimeter

public class Solution {
    public int IslandPerimeter(int[][] grid) {
        int rows = grid.Length;
        int cols = grid[0].Length;
        int perimeter = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    // 检查上方
                    if (i == 0 || grid[i-1][j] == 0) {
                        perimeter++;
                    }
                    // 检查下方
                    if (i == rows-1 || grid[i+1][j] == 0) {
                        perimeter++;
                    }
                    // 检查左方
                    if (j == 0 || grid[i][j-1] == 0) {
                        perimeter++;
                    }
                    // 检查右方
                    if (j == cols-1 || grid[i][j+1] == 0) {
                        perimeter++;
                    }
                }
            }
        }
        
        return perimeter;
    }
}

var islandPerimeter = function(grid) {
    let perimeter = 0;
    const rows = grid.length;
    const cols = grid[0].length;
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 1) {
                let sides = 4;
                
                if (i > 0 && grid[i-1][j] === 1) sides--;
                if (i < rows-1 && grid[i+1][j] === 1) sides--;
                if (j > 0 && grid[i][j-1] === 1) sides--;
                if (j < cols-1 && grid[i][j+1] === 1) sides--;
                
                perimeter += sides;
            }
        }
    }
    
    return perimeter;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历整个网格，m 和 n 分别为网格的行数和列数
空间复杂度O(1)只使用了常数级别的额外空间

相关题目