題目
難度：★★☆☆☆
類(lèi)型：矩陣
給定一個(gè)包含 0 和 1 的二維網(wǎng)格地圖，其中 1 表示陸地 0 表示水域。
網(wǎng)格中的格子水平和垂直方向相連（對(duì)角線(xiàn)方向不相連）。整個(gè)網(wǎng)格被水完全包圍，但其中恰好有一個(gè)島嶼（或者說(shuō)墩剖，一個(gè)或多個(gè)表示陸地的格子相連組成的島嶼）。
島嶼中沒(méi)有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周?chē)乃噙B）酝豪。格子是邊長(zhǎng)為 1 的正方形涛碑。網(wǎng)格為長(zhǎng)方形，且寬度和高度均不超過(guò) 100 孵淘。計(jì)算這個(gè)島嶼的周長(zhǎng)蒲障。
示例
輸入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
輸出: 16
解釋: 它的周長(zhǎng)是下面圖片中的 16 個(gè)黃色的邊：
解答
方案1：計(jì)數(shù)邊長(zhǎng)
島嶼的邊是陸地和海洋的分界面，島嶼的周長(zhǎng)不僅由島嶼的面積決定瘫证，也由每個(gè)島嶼單元（值為1揉阎，邊長(zhǎng)為1的島嶼）之間的相鄰關(guān)系決定，在遍歷到的過(guò)程中背捌，如果遇到一塊陸地毙籽，判斷該陸地單元的上下左右四個(gè)方向是否有海洋或邊界，如果有的話(huà)毡庆，則將最終邊長(zhǎng)加一坑赡。
class Solution:
def islandPerimeter(self, grid):
H, W = len(grid), len(grid[0]) # 獲得區(qū)域的高和寬
side_length = 0 # 邊長(zhǎng)統(tǒng)計(jì)
for h in range(H): # 逐行遍歷
for w in range(W): # 逐列遍歷
if grid[h][w]: # 如果遇到陸地
if h - 1 < 0 or grid[h - 1][w] == 0: # 上邊是地圖邊界或海洋
side_length += 1 # 邊長(zhǎng)+1
if h + 1 >= H or grid[h + 1][w] == 0: # 下邊是地圖邊界或海洋
side_length += 1 # 邊長(zhǎng)+1
if w - 1 < 0 or grid[h][w - 1] == 0: # 左邊是地圖邊界或海洋
side_length += 1 # 邊長(zhǎng)+1
if w + 1 >= W or grid[h][w + 1] == 0: # 右邊是地圖邊界或海洋
side_length += 1 # 邊長(zhǎng)+1
return side_length # 返回陸地邊長(zhǎng)
方案2：只考慮右下
我們也可以只考慮右下方向：
如果遇到島嶼單元，要將周長(zhǎng)+4么抗，默認(rèn)當(dāng)前島嶼單元是個(gè)孤島毅否；
要考慮島嶼單元之間的相鄰關(guān)系，如果遇到右側(cè)或者下方有島嶼單元與當(dāng)前單元相鄰蝇刀，要根據(jù)情況削減周長(zhǎng)：
（1）當(dāng)前島嶼單元只有右側(cè)或只有下方有島嶼單元螟加，則將邊長(zhǎng)-2；
（2）當(dāng)前島嶼單元的右側(cè)和下方均有島嶼單元，說(shuō)明當(dāng)前島嶼單元是內(nèi)陸地區(qū)捆探，需要將周長(zhǎng)-4然爆；
因?yàn)楸苊庵貜?fù)計(jì)算，所以考慮右下兩側(cè)黍图。
class Solution:
def islandPerimeter(self, grid):
H, W = len(grid), len(grid[0]) # 獲得區(qū)域的高和寬
side_length = 0 # 邊長(zhǎng)統(tǒng)計(jì)
for h in range(H): # 逐行遍歷
for w in range(W): # 逐列遍歷
if grid[h][w]: # 如果遇到陸地
side_length += 4 # 邊長(zhǎng)+4
if h+1 < H and grid[h+1][w]: # 如果下方有一塊陸地
side_length -= 2 # 邊長(zhǎng)-2
if w+1 < W and grid[h][w+1]: # 如果右側(cè)有一塊陸地
side_length -= 2 # 邊長(zhǎng)-2
return side_length # 返回陸地邊長(zhǎng)
如有疑問(wèn)或建議曾雕，歡迎評(píng)論區(qū)留言~
