岛屿的周长

2023-12-13 14:59:29

题意:

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

题目来源: https://leetcode.cn/problems/island-perimeter/description/

解题方法:

方法一:遍历每一个节点,如果为陆地,边长贡献值加 4。再寻找其四个方向,每个方向如果是陆地,贡献值减 1

function islandPerimeter($grid) {
    $num = 0;
    for($i = 0; $i < count($grid); $i++){
        for($j = 0; $j < count($grid[$i]); $j++){
            $temp = 4;	//初始化岛屿周长为4
            if($grid[$i][$j] == 1){
                //左边存在相接,直接减1
                if(isset($grid[$i][$j-1]) && $grid[$i][$j-1] == 1){
                    $temp--;
                }
                
                //右边存在相接,直接减1
                if(isset($grid[$i][$j+1]) && $grid[$i][$j+1] == 1){
                    $temp--;
                }
                
                //下边存在相接,直接减1
                if(isset($grid[$i+1][$j]) && $grid[$i+1][$j] == 1){
                    $temp--;
                }
                //上边存在相接,直接减1
                if(isset($grid[$i-1][$j]) && $grid[$i-1][$j] == 1){
                    $temp--;
                }
                $num += $temp;
            }
        }
    }
    return $num;
}

参考:
作者:Vincenzo_Jiang
链接:https://leetcode.cn/problems/island-perimeter/solutions/466512/liang-ci-xun-huan-by-eof-8-2/
来源:力扣(LeetCode)

方法二:与解法一基本相同,只寻找其左侧节点和上面的节点,每个节点的贡献值减少 2.计算量减半

function islandPerimeter($grid) {
    $row = count($grid);
    if($row == 0){
        return 0;
    }
    $col = count(reset($grid));
    $sum = 0;
    // 每个节点的贡献值 左侧有,减2;上面有,也减2
    for($i = 0; $i < $row; $i++){
        for($j = 0; $j < $col; $j++){
            if($grid[$i][$j] == 1){
                $line = 4;
                // 左面
                if(isset($grid[$i][$j-1]) && $grid[$i][$j-1]){
                    $line -= 2;
                }
                // 右面
                if(isset($grid[$i-1][$j]) && $grid[$i-1][$j]){
                    $line -= 2;
                }
                $sum += $line;
            }
        }
    }
    return $sum;
}

参考:
作者:Zou Zhipeng
链接:https://leetcode.cn/problems/island-perimeter/solutions/150539/php-jie-fa-by-zzpwestlife-39/
来源:力扣(LeetCode)

文章来源:https://blog.csdn.net/weixin_43741253/article/details/134952380
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。