岛屿的周长 --leetcode刷题,golang实现

牙哥 · · 637 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。

网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。

岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 :

输入:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

输出: 16

解释: 它的周长是下面图片中的 16 个黄色的边:

island.png

解题思路:
虽然耗时长,内存消耗大,但是是最容易想到的一种方式,遍历切片,如果当前位置是岛屿,总算加4,检查上下左右,如果有相邻岛屿,则总数 -1.
也可以简化为只检查右侧和下面,如果右边是岛屿,-2,如果下面是岛屿,-2,这样只用判断两个方向,而不需要判断四个方向了

代码如下:

func islandPerimeter(grid [][]int) int {
    r, c := len(grid), len(grid[0])
    sum := 0
    for i, row := range grid {
        for j, v := range row {
            if v == 1 {
                sum += 4
                //下方同一列为陆地
                if i + 1 < r && grid[i + 1][j] == 1 {
                    sum -= 2
                }
                //右侧相邻位置为陆地
                if j + 1 < c && grid[i][j + 1] == 1 {
                    sum -= 2
                }
            }
        }
    }
    return sum
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:牙哥

查看原文:岛屿的周长 --leetcode刷题,golang实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

637 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传