[LeetCode] 200. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

找島嶼個數 數字1且上下相連的 算一個島嶼 數字0 算是水域

圖搜索的題目 應該是用 DFS 或是 BFS 做都可以.

DFS 解法大概是在搜索 時遇到相鄰為1的 就mark 上下左右的全為  'P' 並且count 加1

source code 參考 ( https://discuss.leetcode.com/topic/36047/python-simple-dfs-solution )

line 6 : 走一遍 matrix (m x n), 如果cell 為 1, 做dfs

line 14 : 劃定 邊界條件 如果 i, j 超過界了 (小於 0 或是 大於等於 m,n) 或是 cell 不為1了, return

line 16: 別忘了標示 為 'P'. 這裡標為 任何非 1的都可以

line 17 - 20: 向 上,下,左,右 4個方向做dfs

BFS 解法:

用queue 來做 flood fill