图论——求岛屿的最大面积(python)
·
思路:
dfs搜索岛屿的时候,用一个全局变量记录搜索到的岛屿的面积,保留最大值。
#搜索岛屿的最大面积
# 4 5
# 1 1 0 0 0
# 1 1 0 0 0
# 0 0 1 0 0
# 0 0 0 1 1
#输出: 4
def maxIslandArea(grid,m,n):
res=0
visited=[[0]*n for _ in range(m)]
dirs=[(0,1),(0,-1),(1,0),(-1,0)] #四个方向
def dfs(x,y):
nonlocal cur,res
if x<0 or x>=m or y<0 or y>=n: #判断是否越界
return
if grid[x][y]==0 or visited[x][y]==1:
return
cur+=1
visited[x][y]=1
for dx,dy in dirs:
dfs(x+dx,y+dy)
for i in range(m):
for j in range(n):
cur = 0
if grid[i][j]==1 and visited[i][j]==0:
dfs(i,j) #直接递归,判断逻辑交给递归函数内部
res=max(cur,res) #更新全局变量
print(res)
return res
def main():
m,n=map(int,input().split())
grid=[]
for i in range(m):
line=list(map(int,input().split()))
grid.append(line)
maxIslandArea(grid,m,n)
if __name__=="__main__":
main()
更多推荐


所有评论(0)