网站手机自动跳转,青海网站建设哪个最好,wordpress建立仿站,服装高端网站建设文章目录 101.孤岛的总面积102.沉没孤岛103.水流问题正向逻辑反向逻辑 104.建造最大岛屿 101.孤岛的总面积
可以把最外围的都检查一遍是否有为1的#xff0c;有的话就把他接壤的全变成海#xff0c;然后正常算面积。也可以看岛屿是否有靠边的位置#xff0c;有的话该岛面积… 文章目录 101.孤岛的总面积102.沉没孤岛103.水流问题正向逻辑反向逻辑 104.建造最大岛屿 101.孤岛的总面积
可以把最外围的都检查一遍是否有为1的有的话就把他接壤的全变成海然后正常算面积。也可以看岛屿是否有靠边的位置有的话该岛面积不计算在总面积中。
direction [[1, 0], [0, 1], [-1, 0], [0, -1]]
def bfs(cur, islands, visited):N len(islands)M len(islands[0])st [cur]area 1flag Falseif cur[0]0 or cur[0]N-1 or cur[1]0 or cur[1]M-1:flag Truewhile st:cur st.pop()for d in direction:x d[0] cur[0]y d[1] cur[1]if x 0 or x N or y 0 or y M:continueif islands[x][y] 1 and visited[x][y] False:if x0 or xN-1 or y0 or yM-1:flag Truearea 1st.append([x, y])visited[x][y] Trueif flag:return 0else:return area
if __name__ __main__:area 0NM input().split()N, M int(NM[0]), int(NM[1])islands [[0] * M for _ in range(N)]for i in range(N):lands input().split()for j in range(M):islands[i][j] int(lands[j])visited [[False] * M for _ in range(N)]for i in range(N):for j in range(M):if (islands[i][j] 1) and (visited[i][j]False):visited[i][j] Truetmp bfs([i,j], islands, visited)# print([i, j], tmp)area tmpprint(area)102.沉没孤岛
这题就是从外圈找找到未访问且为1的就把接壤的在新的岛屿图上标注为1。
direction [[1, 0], [0, 1], [-1, 0], [0, -1]]def bfs(cur, islands, visited, new_islands):N len(islands)M len(islands[0])st [cur]while st:cur st.pop()for d in direction:x d[0] cur[0]y d[1] cur[1]if x 0 or x N or y 0 or y M:continueif islands[x][y] 1 and visited[x][y] False:st.append([x, y])visited[x][y] Truenew_islands[x][y] 1
if __name__ __main__:area 0NM input().split()N, M int(NM[0]), int(NM[1])islands [[0] * M for _ in range(N)]for i in range(N):lands input().split()for j in range(M):islands[i][j] int(lands[j])visited [[False] * M for _ in range(N)]new_islands [[0] * M for _ in range(N)]for j in range(M):if islands[0][j] 1 and not visited[0][j]:new_islands[0][j] 1bfs([0, j], islands, visited, new_islands)if islands[N-1][j] 1 and not visited[N-1][j]:new_islands[N-1][j] 1bfs([N-1, j], islands, visited, new_islands)for i in range(1, N-1):if islands[i][0] 1 and not visited[i][0]:new_islands[i][0] 1bfs([i, 0], islands, visited, new_islands)if islands[i][M-1] 1 and not visited[i][M-1]:new_islands[i][M-1] 1bfs([i, M-1], islands, visited, new_islands)for island in new_islands:print( .join(map(str, island)))103.水流问题
正向逻辑
正向逻辑就是对每一块去看他能流到哪里如果同时能流到第一边界和第二边界那就输出。但是会超时。
def dfs(cur, grid, visited):if visited[cur[0]][cur[1]]:returnvisited[cur[0]][cur[1]] TrueN len(grid)M len(grid[0])directions [[1,0], [-1,0],[0,1], [0,-1]]for d in directions:x cur[0] d[0]y cur[1] d[1]if x 0 or x N or y 0 or y M:continueif grid[x][y] grid[cur[0]][cur[1]]:dfs([x, y], grid, visited)def flow2Borad(cur, grid):N len(grid)M len(grid[0])visited [[False] * M for _ in range(N)]dfs(cur, grid, visited)isFirst FalseisSec Falsefor i in range(M):if visited[0][i]:isFirst Truebreakif not isFirst:for i in range(N):if visited[i][0]:isFirst Truebreakfor i in range(M):if visited[N-1][i]:isSec Truebreakif not isSec:for i in range(N):if visited[i][M-1]:isSec Truebreak if isSec and isFirst:return Trueelse:return False
if __name__ __main__:area 0NM input().split()N, M int(NM[0]), int(NM[1])islands [[0] * M for _ in range(N)]for i in range(N):lands input().split()for j in range(M):islands[i][j] int(lands[j])for i in range(N):for j in range(M):if flow2Borad([i,j], islands):print(str(i), ,str(j))
反向逻辑
对第一边界和第二边界的格子往回推导退出哪些格子能够流到第一边界和第二边界如果一个格子能流到第一边界并且可以流到第二边界那就输出他。
def dfs(cur, islands, visited):if visited[cur[0]][cur[1]]:returnN len(islands)M len(islands[0])visited[cur[0]][cur[1]] Truedirections [[1,0], [-1,0], [0,1], [0,-1]]for d in directions:x cur[0] d[0]y cur[1] d[1]if x 0 or x N or y 0 or y M:continueif islands[x][y] islands[cur[0]][cur[1]]:continuedfs([x,y], islands, visited)if __name__ __main__:N, M map(int, input().split())islands [[0] * M for _ in range(N)]for i in range(N):lands input().split()for j in range(M):islands[i][j] int(lands[j])isFirst_Borad [[False] * M for _ in range(N)]isSec_Board [[False] * M for _ in range(N)]for i in range(N):dfs([i, 0], islands, isFirst_Borad)dfs([i, M-1], islands, isSec_Board)for j in range(M):dfs([0, j], islands, isFirst_Borad)dfs([N-1, j], islands, isSec_Board)for i in range(N):for j in range(M):if isSec_Board[i][j] and isFirst_Borad[i][j]:print(str(i) str(j))104.建造最大岛屿
有点麻烦的这题在前面的基础上还要再做一个列表来对岛屿进行标号。在计算完所有岛屿面积后做出一个岛屿标号和面积的字典然后遍历所有的位置如果是海洋则在他四周找岛屿没找到一个不同标号的岛屿就加到结果中最后选最大的一个岛屿面积和。但是题目说没有岛输出0但是答案又是1就是默认没有岛屿就翻转一块位置变成岛屿
direction [[1, 0], [0, 1], [-1, 0], [0, -1]]def bfs(cur, islands, visited, mark, num):visited[cur[0]][cur[1]] Truemark[cur[0]][cur[1]] numst [cur]area 1while st:cur st.pop()for d in direction:x d[0] cur[0]y d[1] cur[1]if x 0 or x N or y 0 or y M:continueif islands[x][y] 1 and visited[x][y] False:st.append([x, y])area 1visited[x][y] Truemark[x][y] numreturn areaif __name__ __main__:N, M map(int, input().split())islands [[0] * M for _ in range(N)]for i in range(N):lands input().split()for j in range(M):islands[i][j] int(lands[j])visited [[False] * M for _ in range(N)]mark [[0] * M for _ in range(N)]num 1islandArea {}for i in range(N):for j in range(M):if (islands[i][j] 1) and (visited[i][j]False):area bfs([i,j], islands, visited, mark, num)islandArea[num] areanum 1directions [[1,0], [-1,0], [0,1], [0,-1]]if islandArea:result max([value for value in islandArea.values()])for i in range(N):for j in range(M):if islands[i][j] 0:temp 1pre []for d in directions:nextx i d[0]nexty j d[1]if nextx 0 or nextx N or nexty 0 or nexty M:continue if islands[nextx][nexty] 1 and not mark[nextx][nexty] in pre:temp islandArea[mark[nextx][nexty]]pre.append(mark[nextx][nexty])result max(result, temp)print(result)else:print(1)
