前往
大廳
主題

LeetCode - 463. Island Perimeter 解題心得

Not In My Back Yard | 2020-10-29 00:00:02 | 巴幣 0 | 人氣 301

題目連結:


題目意譯:
給定你代表一個地圖的 row × col 之網格 grid,其中 grid[i][j] = 1 代表陸地、grid[i][j] = 0 代表水。

網格的每個格子都與其垂直方向、水平方向(對角線方向則沒有)的相鄰格子連接著。整個網格被水所包覆起來,且只有一座島(即一個或多個陸地格子連接在一起)。

該座島沒有「湖」,「湖」意味著島中的水域且沒有與環繞著島的水域相通。每個格子為一邊長為 1 的正方形。網格為長方形,且長與寬都不超過 100。判斷這座島嶼的周長。

限制:
row == grid.length
col == grid[i].length
1 ≦ row, col ≦ 100
grid[i][j] 為 0 或是 1。



範例測資:
範例 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


解題思維:
掃過整個地圖,對於當中的每格陸地,看看其上下左右的相鄰格子有多少格是陸地(假設有 L 格),則本格陸地會貢獻 4 - L 單位長的周長(代表它有 4 - L 靠水(如範例 1 中的黃線))。

將所有陸地貢獻的周長全部加起來即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作