九章演算法 | Facebook 面試題 : 島的周長

01-30

撰文 | JZ

專欄 | 九章演算法

題目描述

以二維整數網格的形式給出地圖，1代表陸地，0代表水。

網格單元水平/垂直連接（不包含對角）。

整張地圖被水完全包圍，並且有一個島（即一個或多個連接的陸地單元）。

島上沒有「湖泊」（裡面的水沒有連接到島外的水）。

一個單元格是邊長為1的正方形。網格為矩形，寬度和高度不超過100。

確定島嶼的周長。

輸入：n[[0,1,0,0],n [1,1,1,0],n [0,1,0,0],n [1,1,0,0]]n n輸出：n 16n

樣例解釋：
樣例輸入的島嶼的周長為16，如圖中黃線所示。

2.1 題目中對於周長的定義為陸地和水邊界的地方，那麼我們就能模擬題意，枚舉所有的格子，對於每個為陸地的格子，判斷周圍有幾個格子為水就行了。那麼檢查上下左右四個格子看是否有陸地相鄰，如果沒有陸地相鄰那麼就是水。

2.2這道題在遍歷上下左右的時候一般同學可能去枚舉，但是枚舉寫這道題代碼風格並不太好，像這種如果能夠想到用for循環的方式來遍歷，並且把判斷條件用獨立模塊實現，那麼就是一個非常好的代碼風格的體現。

2.3由於要枚舉每個格子，所以時間複雜度為O(nm),n，m為圖的寬度與高度。

這道題目主要是代碼風格的考察，如果能夠使用for循環來代替if判斷實現上下左右四個格子，那麼面試官會眼前一亮，給你一個非常好的評價。

http://www.jiuzhang.com/solutions/island-perimeter/