前往
大廳
主題

LeetCode - 1020. Number of Enclaves 解題心得

Not In My Back Yard | 2022-10-14 12:00:07 | 巴幣 0 | 人氣 175

題目連結:


題目意譯:
你被給定一個 m × n 的二元陣列 grid,其中 0 代表著一個海洋格子而 1 則代表一個陸地格子。

一「步」是由從一個陸地格子走到另一個相鄰(四個方向的)的陸地格子或是走到 grid 的邊界之外所組成。

回傳 grid 中有多少陸地格子無論走多少步都無法走到 grid 的邊界之外。

限制:
m == grid.length
n == grid[i].length
1 ≦ m, n ≦ 500
grid[i][j] 只會是 0 或是 1。



範例測資:
範例 1:
輸入: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
輸出: 3
解釋: 有三個 1 被 0 包圍住,而有一個 1 沒有被包住因為其位於邊界上。

範例 2:
輸入: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
輸出: 0
解釋: 所有 1 要不是就是位於邊界上,不然就是可以抵達邊界。


解題思維:
昨天的題目很像,利用廣度優先搜尋(Breadth First Search,BFS)的精神找出每個「島嶼」(也就是聚在一起的 1 們),然後在過程中判斷有沒有超出邊界。如果沒有就代表這個島嶼所有的 1 都走不出邊界,因此不會貢獻任何值到答案之中;反之,則代表這個島嶼中所有的 1 都可以經由若干步走到邊界並走出去,因此其將貢獻到答案之中,其值恰為該島嶼之「面積」(即這群 1 的總數量)。




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

創作回應

更多創作