題目連結:
題目意譯:
給定一個二維網格 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 圍繞著)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。