463. Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],

[1,1,1,0], [0,1,0,0], [1,1,0,0]] Answer: 16 Explanation: The perimeter is the 16 yellow stripes in the image below:

463. Island Perimeter

一开始的思路是,循环遍历每一个1方格,看它的上下左右是否为0,如果为0或上下左右是边界,则边数加1。后来看了Discuss里的思路,
统计1方格的个数,记为q。遍历每一个1方格,看它的右和下是否也为1。如果为1,则为邻居。统计全部1方格的右邻居和下邻居个数,记为p。最后的边界数为q * 4 – p * 2。相当于减去了公用边的个数。
代码如下:

grid)        col = len(grid[0])        p = 0        q = 0        for i in range(0, row):            for j in range(0, col):                if grid[i][j] == 1:                    q += 1                        if i+1 < row and grid[i+1][j] == 1:                        p += 1                    if j+1 < col and grid[i][j+1] == 1:                        p += 1        return q * 4 - p * 2

Original: https://blog.51cto.com/u_15762852/5613275
Author: mb6304a73bed12a
Title: 463. Island Perimeter

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/508377/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球