岛屿的周长
题意:
给定一个 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
题目来源: 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)
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!