代码随想录算法训练营DAY58｜101.孤岛的总面积、102.沉没孤岛、103. 水流问题、104.建造最大岛屿

忙。。。写了好久。。。。慢慢补吧。

101.孤岛的总面积

• 先把周边的岛屿变成水
• dfs

def dfs(x, y, graph, s):if x<0 or x>=len(graph) or y<0 or y>=len(graph[0]) or graph[x][y]==0:return sgraph[x][y]=0s+=1s = dfs(x+1, y, graph, s)s = dfs(x-1, y, graph, s)s = dfs(x, y+1, graph, s)s = dfs(x, y-1, graph, s)return sif __name__=='__main__':n,m = map(int,input().split())graph=[]for i in range(n):row = list(map(int, input().split()))graph.append(row)for i in range(n):if graph[i][0]==1:dfs(i,0,graph,0)if graph[i][m-1]==1:dfs(i,m-1,graph,0)for j in range(m):if graph[0][j]==1:dfs(0,j,graph,0)if graph[n-1][j]==1:dfs(n-1,j,graph,0)s_t = 0for x in range(n):for y in range(m):if graph[x][y]==1:s=dfs(x,y,graph,0)s_t+=sprint(s_t)

102.沉没孤岛

from collections import dequedef bfs(x, y, graph):graph[x][y]=2que = deque([[x,y]])while que:x, y = que.popleft()directions = [[0,1],[0,-1],[1,0],[-1,0]]for k in range(4):x0, y0 = directions[k]new_x = x+x0new_y = y+y0if new_x>=0 and new_x<len(graph) and new_y>=0 and new_y<len(graph[0]) and graph[new_x][new_y]==1:que.append([new_x, new_y])graph[new_x][new_y]=2return     if __name__=='__main__':n,m = map(int,input().split())graph=[]for _ in range(n):row = list(map(int, input().split()))graph.append(row)    for i in range(n):if graph[i][0]==1:bfs(i,0,graph)if graph[i][m-1]==1:bfs(i,m-1,graph)for j in range(m):if graph[0][j]==1:bfs(0,j,graph)if graph[n-1][j]==1:bfs(n-1,j,graph)for x in range(n):for y in range(m):if graph[x][y]==2:graph[x][y]=1elif graph[x][y]==1:graph[x][y]=0for a in range(n):for b in range(m):print(str(graph[a][b])+' ',end = '')print()

103. 水流问题

• 注意是从边界逆流而上，判断条件应该是graph[x][y]<=graph[new_x][new_y]:

def dfs(x,y,graph,bordermatrix):if bordermatrix[x][y]:returnbordermatrix[x][y]=1directions=[[0,1],[0,-1],[1,0],[-1,0]]for i in range(4):x0,y0=directions[i]new_x = x+x0new_y = y+y0if new_x<0 or new_x>=len(graph) or new_y<0 or new_y>=len(graph[0]):continueif graph[x][y]<=graph[new_x][new_y]:dfs(new_x,new_y,graph,bordermatrix)return if __name__=='__main__':n,m=map(int, input().split())graph=[]for _ in range(n):row = list(map(int, input().split()))graph.append(row)firstborder=[[0]*m for i in range(n)]secondborder=[[0]*m for i in range(n)]for i in range(n):dfs(i,0,graph,firstborder)dfs(i,m-1,graph,secondborder)for j in range(m):dfs(0,j,graph,firstborder)dfs(n-1,j,graph,secondborder)for k in range(n):for l in range(m):if firstborder[k][l] and secondborder[k][l]:print('{} {}'.format(str(k),str(l)))

104.建造最大岛屿

def dfs(x,y,graph,visited,mark,s):directions=[[0,1],[0,-1],[1,0],[-1,0]]if visited[x][y] or not graph[x][y]:return  svisited[x][y]=Truegraph[x][y]=marks+=1for i in range(4):x0,y0=directions[i]new_x = x+x0new_y = y+y0if new_x<0 or new_x>=len(graph) or new_y<0 or new_y>=len(graph[0]):continues = dfs(new_x,new_y,graph,visited,mark,s)return sif __name__=='__main__':n,m = map(int, input().split())graph = []for i in range(n):row = list(map(int, input().split()))graph.append(row)isallgrid=Truevisited=[[False]*m for i in range(n)]islands={}islands[0]=0idx=1for j in range(n):for k in range(m):if graph[j][k]==1:s = dfs(j,k,graph,visited,idx,0)islands[idx]=sidx+=1else:isallgrid=Falseif isallgrid:print(m*n)else:result = 0for j in range(n):for k in range(m):count = 1visitedgraph=[]if graph[j][k]==0:directions=[[0,1],[0,-1],[1,0],[-1,0]]for l in range(4):j0,k0 = directions[l]new_j = j+j0new_k = k+k0if new_j<0 or new_j>=len(graph) or new_k<0 or new_k>=len(graph[0]):continueif graph[new_j][new_k] in visitedgraph: continuecount+=islands[graph[new_j][new_k]]visitedgraph.append(graph[new_j][new_k])result = max(result, count)print(result)