給定一個(gè)包含了一些 0 和 1的非空二維數(shù)組 grid , 一個(gè) 島嶼 是由四個(gè)方向 (水平或垂直) 的 1 (代表土地) 構(gòu)成的組合刑然。你可以假設(shè)二維矩陣的四個(gè)邊緣都被水包圍著部翘。
找到給定的二維數(shù)組中最大的島嶼面積。(如果沒(méi)有島嶼科平，則返回面積為0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
對(duì)于上面這個(gè)給定矩陣應(yīng)返回 6姜性。注意答案不應(yīng)該是11瞪慧，因?yàn)閸u嶼只能包含水平或垂直的四個(gè)方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
對(duì)于上面這個(gè)給定的矩陣, 返回 0部念。
注意: 給定的矩陣grid 的長(zhǎng)度和寬度都不超過(guò) 50弃酌。
"""
分析(DFS)：首先找到目標(biāo)點(diǎn)氨菇，然后從目標(biāo)點(diǎn)發(fā)散開(kāi)[上下左右四個(gè)方向]。
然后當(dāng)我們到達(dá)新的方向之后怎么辦妓湘？繼續(xù)DFS查蓉，那就是遞歸咯。
遞歸邊界條件：數(shù)組是不越界榜贴，對(duì)應(yīng)值為1豌研，之前沒(méi)有找到過(guò)這個(gè)點(diǎn)
用一個(gè)set保存已經(jīng)遞歸過(guò)的點(diǎn),下次遇到直接跳過(guò)
"""
class Solution:
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
seen = set() # 保存已經(jīng)探查過(guò)的點(diǎn)
mx = 0
def dfs(grid, i, j):
'''
遞歸完成四個(gè)方向搜索
'''
area = 0
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == 1 and (i, j) not in seen:# 邊界條件
seen.add((i, j))
area = 1 + dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1)
return area
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1 and (i, j) not in seen:
mx = max(mx, dfs(grid, i, j))
return mx
