leetcode695 岛屿的最大面积
使用dfs,遍历grid当为1的时候，就通过dfs看这个岛屿的面积有多大，最后比较选出最大的一个。
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
def dfs(x,y,visit,count):
if grid[x][y]==1:
visit[x][y]=1
count+=1
else:
return count
for item in [(0,1),(1,0),(-1,0),(0,-1)]:
if 0<=x+item[0]<len(grid) and 0<=y+item[1]<len(grid[0]) and visit[x+item[0]][y+item[1]]!=1 and grid[x+item[0]][y+item[1]]!=0:
count=dfs(x+item[0],y+item[1],visit,count)
return count
maxvalue=0
visit=[[0]*len(grid[0]) for _ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==1:
maxvalue=max(maxvalue, dfs(i,j,visit,0))
return maxvalue使用栈，可以类比使用队列。
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
stack=[]
maxvalue=0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==1:
count=1
grid[i][j]=0
stack.append((i,j))
while stack:
x,y=stack.pop()
for item in [(1,0),(0,1),(-1,0),(0,-1)]:
if 0<=x+item[0]<len(grid) and 0<=y+item[1]<len(grid[0]) and grid[x+item[0]][y+item[1]]==1:
grid[x+item[0]][y+item[1]]=0
stack.append((x+item[0],y+item[1]))
count+=1
maxvalue=max(maxvalue,count)
return maxvalue使用队列，只把栈的pop()改成pop(0)即可。
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
stack=[]
maxvalue=0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==1:
count=1
grid[i][j]=0
stack.append((i,j))
while stack:
x,y=stack.pop(0)
for item in [(1,0),(0,1),(-1,0),(0,-1)]:
if 0<=x+item[0]<len(grid) and 0<=y+item[1]<len(grid[0]) and grid[x+item[0]][y+item[1]]==1:
grid[x+item[0]][y+item[1]]=0
stack.append((x+item[0],y+item[1]))
count+=1
maxvalue=max(maxvalue,count)
return maxvalue
