网络推广协议_h5开发app用什么工具好_深圳seo排名_seo百度快速排名软件

思路：当判断当前岛屿已经触及边缘时，仍然遍历标记，但最后返回面积时返回0，使用flag标识有没有触及边缘

#所有单元格都不接触边缘 如果触及边缘时使面积返回0
from collections import deque
def countArea(i,j,graph,n,m):flag=1 dq=deque()dq.append([i,j])graph[i][j]=-1tempRes=1while len(dq)>0:temp=dq.popleft()if temp[0]==0 or temp[0]==n-1 or temp[1]==0 or temp[1]==m-1:flag=0if temp[0]>0 and graph[temp[0]-1][temp[1]]==1:graph[temp[0]-1][temp[1]]=-1dq.append([temp[0]-1,temp[1]])tempRes+=1if temp[0]<n-1 and graph[temp[0]+1][temp[1]]==1:graph[temp[0]+1][temp[1]]=-1dq.append([temp[0]+1,temp[1]])tempRes+=1if temp[1]>0 and graph[temp[0]][temp[1]-1]==1:graph[temp[0]][temp[1]-1]=-1dq.append([temp[0],temp[1]-1])tempRes+=1if temp[1]<m-1 and graph[temp[0]][temp[1]+1]==1:graph[temp[0]][temp[1]+1]=-1dq.append([temp[0],temp[1]+1])tempRes+=1if flag==0:return flagelse:return tempResdef main():n,m=map(int,input().split())graph=[[0]*m for _ in range(n)]for i in range(n):graph[i]=list(map(int,input().split()))res=0    for i in range(n):for j in range(m):if graph[i][j]==1:res+= countArea(i,j,graph,n,m)print(res)if __name__=="__main__":main()

# 先判断是不是孤岛 如果是孤岛才标记（先记录一下）
#实际做法是 先标记（避免死循环）且记录，如果不是孤岛就再变回1
from collections import deque
def countArea(i,j,graph,n,m):flag=1 dq=deque()dq.append([i,j])graph[i][j]=0tempRes=[[i,j]]while len(dq)>0:temp=dq.popleft()if temp[0]==0 or temp[0]==n-1 or temp[1]==0 or temp[1]==m-1:flag=0if temp[0]>0 and graph[temp[0]-1][temp[1]]==1:graph[temp[0]-1][temp[1]]=0dq.append([temp[0]-1,temp[1]])tempRes.append([temp[0]-1,temp[1]])if temp[0]<n-1 and graph[temp[0]+1][temp[1]]==1:graph[temp[0]+1][temp[1]]=0dq.append([temp[0]+1,temp[1]])tempRes.append([temp[0]+1,temp[1]])if temp[1]>0 and graph[temp[0]][temp[1]-1]==1:graph[temp[0]][temp[1]-1]=0dq.append([temp[0],temp[1]-1])tempRes.append([temp[0],temp[1]-1])if temp[1]<m-1 and graph[temp[0]][temp[1]+1]==1:graph[temp[0]][temp[1]+1]=0dq.append([temp[0],temp[1]+1])tempRes.append([temp[0],temp[1]+1])if flag==0:for a,b in tempRes:graph[a][b]=1returndef main():n,m=map(int,input().split())graph=[[0]*m for _ in range(n)]for i in range(n):graph[i]=list(map(int,input().split()))for i in range(n):for j in range(m):if graph[i][j]==1:countArea(i,j,graph,n,m)for i in range(n):print(' '.join(str(item) for item in graph[i]))if __name__=="__main__":main()

正确题解：

first = set()
second = set()
directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]def dfs(i, j, graph, visited, side):if visited[i][j]:returnvisited[i][j] = Trueside.add((i, j))for x, y in directions:new_x = i + xnew_y = j + yif (0 <= new_x < len(graph)and 0 <= new_y < len(graph[0])and int(graph[new_x][new_y]) >= int(graph[i][j])):dfs(new_x, new_y, graph, visited, side)def main():global firstglobal secondN, M = map(int, input().strip().split())graph = []for _ in range(N):row = input().strip().split()graph.append(row)# 是否可到达第一边界visited = [[False] * M for _ in range(N)]for i in range(M):dfs(0, i, graph, visited, first)for i in range(N):dfs(i, 0, graph, visited, first)# 是否可到达第二边界visited = [[False] * M for _ in range(N)]for i in range(M):dfs(N - 1, i, graph, visited, second)for i in range(N):dfs(i, M - 1, graph, visited, second)# 可到达第一边界和第二边界res = first & secondfor x, y in res:print(f"{x} {y}")if __name__ == "__main__":main()

自己的错误题解：

#从每个点深搜，能同时到达上左和下右#可以不可以倒着来第一边界能到的点拉出来 第二边界能找的点也拉出来
# 第一边界 [0][j]    [i][0] 
# 第二边界 [n-1][j]  [i][m-1]from collections import deque
def mark(i,j,graph,n,m,flag):dq=deque()dq.append([i,j])tempRes=[[i,j]]while len(dq)>0:a,b=dq.popleft()if flag==1:if a<n-1 and graph[a+1][b]>=graph[a][b]:dq.append([a+1,b])tempRes.append([a+1,b])if b<m-1 and graph[a][b+1]>=graph[a][b]:dq.append([a,b+1])tempRes.append([a,b+1])else:if a>0 and graph[a-1][b]>=graph[a][b]:dq.append([a-1,b])tempRes.append([a-1,b])if b>0 and graph[a][b-1]>=graph[a][b]:dq.append([a,b-1])tempRes.append([a,b-1]) return tempResdef main():n,m=map(int,input().split())graph=[[0]*m for _ in range(n)]for i in range(n):graph[i]=list(map(int,input().split()))res=[]first=[]second=[]for i in range(n):first+=mark(i,0,graph,n,m,1)second+=mark(i,m-1,graph,n,m,2)for j in range(m):first+=(mark(0,j,graph,n,m,1))second+=(mark(n-1,j,graph,n,m,2))res=list(filter(lambda x: x in first, second))res=[list(item) for item in set(tuple(r) for r  in res)]for r in res:print(' '.join(str(item) for item in r))if __name__=="__main__":main()

#暴力解：遍历每个非1点，将其变为1后，求一次从该点出发的最大岛屿
#优化思路：
#1.给岛屿打标，记录不同标记的岛屿的面积
#2.将一个0点变成1，合并相邻点岛屿的面积
direction=[[-1,0],[1,0],[0,-1],[0,1]]def countArea(i,j,graph,n,m,mark):area=0if graph[i][j]==1:area+=1graph[i][j]=markfor d in direction:x=i+d[0]y=j+d[1]if 0<=x<=n-1 and 0<=y<=m-1:area+=countArea(x,y,graph,n,m,mark)return areadef main():n,m=map(int,input().split())graph=[[0]*m for _ in range(n)]for i in range(n):graph[i]=list(map(int,input().split()))mark=2dict={}for i in range(n):for j in range(m):if graph[i][j]==1:area=countArea(i,j,graph,n,m,mark)dict[mark]=areamark+=1res=0if len(dict)>0:res=max(dict.values())for i in range(n):for j in range(m):if graph[i][j]==0:tempRes=1visited=set()for d in direction:x=i+d[0]y=j+d[1]if 0<=x<=n-1 and 0<=y<=m-1 and graph[x][y]!=0 and graph[x][y] not in visited :visited.add(graph[x][y])tempRes+=dict[graph[x][y]]res=max(res,tempRes)print(res)if __name__=="__main__":main()