200. 島嶼數(shù)量
題目來源：https://leetcode-cn.com/problems/number-of-islands/
題目
給你一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格疟位，請你計算網(wǎng)格中島嶼的數(shù)量毅往。
島嶼總是被水包圍铃剔，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成嵌言。
此外剔氏，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍为朋。
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1
示例 2:
輸入:
11000
11000
00100
00011
輸出: 3
解釋: 每座島嶼只能由水平和/或豎直方向上相鄰的陸地連接而成疤孕。
解題思路
方法一：深度優(yōu)先搜索
當(dāng)要求出島嶼的數(shù)量時慌核，我們可以掃描題目給出的二維網(wǎng)格距境。如果遍歷的元素為 1，則以這個位置為起點進(jìn)行深度優(yōu)先搜索垮卓。
這里需要注意的是：深度優(yōu)先搜索的過程中垫桂，已經(jīng)搜索到的 1 要標(biāo)記為 0，表示已經(jīng)訪問過粟按。
那么進(jìn)行深度優(yōu)先搜索的次數(shù)就是要求的島嶼的數(shù)量诬滩。
詳細(xì)部分見代碼注釋霹粥。
方法二：廣度優(yōu)先搜索
同樣的，這道題也可以使用廣度優(yōu)先搜索進(jìn)行替換解答疼鸟。不過后控，這里需要增加一個輔助隊列。
同樣的空镜，求島嶼的數(shù)量浩淘，先掃描遍歷二維網(wǎng)格，如果遍歷的位置元素為 1吴攒，要將其加入隊列张抄，同時標(biāo)記為訪問過，這里同樣避免重復(fù)被加入隊列中洼怔，導(dǎo)致代碼運行超時欣鳖。（如果遇到超時的情況，可檢查隊列中的變化是否有重復(fù)添加的現(xiàn)象茴厉。）直到隊列為空時泽台，搜索結(jié)束。
同樣進(jìn)行廣度優(yōu)先搜索的次數(shù)就是要求的島嶼數(shù)量矾缓。
文字表述比較繁瑣難懂怀酷，可以結(jié)合代碼了解思想。
具體的代碼實現(xiàn)如下嗜闻。
代碼實現(xiàn)
方法一: 深度優(yōu)先搜索 | 代碼實現(xiàn)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
# 四個方位
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def _dfs(grid, x, y):
# 進(jìn)行深度優(yōu)化搜索蜕依，標(biāo)記已訪問
grid[x][y] = '0'
for dx, dy in directions:
nx = x + dx
ny = y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
_dfs(grid, nx, ny)
ans = 0
for x in range(m):
for y in range(n):
# 遍歷，當(dāng)為陸地時琉雳，進(jìn)行深度優(yōu)化搜索
if grid[x][y] == '1':
ans += 1
_dfs(grid, x, y)
return ans
方法二: 廣度優(yōu)先搜索 | 代碼實現(xiàn)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
from collections import deque
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
ans = 0
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for row in range(m):
for col in range(n):
# 掃描遍歷样眠，
# 當(dāng)為陸地，進(jìn)行廣度優(yōu)化搜索
if grid[row][col] == '1':
ans += 1
# 標(biāo)記已經(jīng)訪問
grid[row][col] = '0'
# 創(chuàng)建輔助隊列翠肘，同時防止重復(fù)搜索
queue = deque([(row, col)])
# 隊列不為空的情況下檐束，繼續(xù)進(jìn)行搜索
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx = x + dx
ny = y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
# 入隊列，防止重復(fù)
queue.append((nx, ny))
# 標(biāo)記已訪問
grid[nx][ny] = '0'
return ans
實現(xiàn)結(jié)果
方法一: 深度優(yōu)先搜索 | 實現(xiàn)結(jié)果
方法二: 廣度優(yōu)先搜索 | 實現(xiàn)結(jié)果
以上就是使用深度優(yōu)先搜索或廣度優(yōu)先搜索的思想束倍，解決《200. 島嶼數(shù)量》問題的主要內(nèi)容被丧。主要需要注意的地方是：當(dāng)已經(jīng)搜索的地方，需要及時標(biāo)記绪妹，避免重復(fù)搜索甥桂。
歡迎關(guān)注微信公眾號《書所集錄》
