ETH官方钱包

前往
大廳
主題

LeetCode - 1254. Number of Closed Islands 解題心得

Not In My Back Yard | 2022-10-13 12:00:20 | 巴幣 110 | 人氣 336

題目連結:


題目意譯:
給定一個二維網格 grid,其由 0(陸地)和 1(水域)組成。一個島嶼為一群 0 四方向相鄰的最大群體,而一個封閉島嶼為一個完全被 1 環繞著的島嶼(上下左右都是)。

回傳封閉島嶼的數量。

限制:
1 ≦ grid.length, grid[0].length ≦ 100
0 ≦ grid[i][j] ≦1



範例測資:
範例 1:
輸入: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
輸出: 2
解釋:
灰色區域是封閉的,因為它們完全被水域(1 所組成的群組)包圍。

範例 2:
輸入: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
輸出: 1

範例 3:
輸入: grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
輸出: 2


解題思維:
其實就跟這題基本上一樣。只是現在在廣度優先搜尋(Breadth First Search,BFS)找單一一個島嶼的過程中,可以檢查擴張的時候有沒有曾經「超出網格邊界」(也就是擴張後的索引值不是 grid 應有的索引值)。

如果沒有的話,代表著這個島嶼即是一個封閉島嶼(因為代表著其四周必定是 1,不然就可以繼續擴張);反之,則代表現在找到的這個島嶼不是一個封閉島嶼(因為超出邊界的那個「地方」本身就代表著該島嶼沒有被 1 圍繞著)。




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

創作回應

更多創作