前往
大廳
主題

LeetCode - 200. Number of Islands 解題心得

Not In My Back Yard | 2022-08-22 12:00:07 | 巴幣 100 | 人氣 146

題目連結:


題目意譯:
給定一個大小 m × n 的二維二元網格 grid,其代表著 '1'(陸地)和 '0'(水域)的地圖,回傳島嶼的個數。

一座島嶼為連接水平或鉛直方向相鄰的陸地並被水域包圍的陸塊。你可以假設 grid 的四個邊被水包圍。

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



範例測資:
範例 1:
輸入: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
輸出: 1

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


解題思維:
經典的廣度優先搜尋(Breadth First Search,BFS)題型,基本上與這題雷同。只是現在不需要求島嶼的最大面積,只需要求島嶼個數即可。




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

創作回應

更多創作