200. 島嶼數(shù)量

你一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，請你計(jì)算網(wǎng)格中島嶼的數(shù)量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

?

示例 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

這道題蠻重要的，頻率蠻高，做個標(biāo)記吧，dfs就行，遍歷過的話就將這個設(shè)置為0

class?Solution:

????def?numIslands(self,?grid:?List[List[str]])?->?int:

????????clen=len(grid)

????????llen=len(grid[0])

????????def?dfs(grid,i,j):

????????????if?not?0<=i<clen?or?not?0<=j<llen?or?grid[i][j]=='0':

????????????????return

????????????grid[i][j]='0'

????????????dfs(grid,i+1,j)

????????????dfs(grid,i-1,j)

????????????dfs(grid,i,j+1)

????????????dfs(grid,i,j-1)

????????res=0

????????for?i?in?range(clen):

????????????for?j?in?range(llen):

????????????????if?grid[i][j]=='1':

????????????????????dfs(grid,i,j)

????????????????????res+=1

????????return?res

后面進(jìn)行了一個剪枝，就是先判斷能不能去，不為1的就不去。

優(yōu)化后大概是優(yōu)化了1/3這樣，還不錯的