asp跳转到别的网站,如何建设合法的网站,微信小程序 编程,网站备案 电信文章目录 101. 孤岛的总面积102. 沉没孤岛103. 水流问题104.建造最大岛屿 101. 孤岛的总面积
卡码网 101. 孤岛的总面积 代码随想录
from collections import deque
n, m map(int, input().split())matrix []for i in range(n):matrix.append(list(map(int, input().split(… 文章目录 101. 孤岛的总面积102. 沉没孤岛103. 水流问题104.建造最大岛屿 101. 孤岛的总面积
卡码网 101. 孤岛的总面积 代码随想录
from collections import deque
n, m map(int, input().split())matrix []for i in range(n):matrix.append(list(map(int, input().split())))visited [[False] * m for _ in range(n)]directions [[1,0],[-1,0],[0,-1],[0,1]]def bfs(matrix, visited, x, y):area 1que deque([])que.append([x,y])flag Falsewhile que:# 弹出一个点cur_x, cur_y que.popleft()if cur_x 0 or cur_x len(matrix)-1 or cur_y 0 or cur_y len(matrix[0])-1:flag True # 计算面积的同时判断是不是处理边界如果是处于边界的话就多返回一个true只有不是边界的情况下才加到总面积上去。# 四个方向遍历四个方向for i, j in directions:next_x cur_x inext_y cur_y jif next_x 0 or next_x len(matrix) or next_y 0 or next_y len(matrix[0]):continueif not visited[next_x][next_y] and matrix[next_x][next_y] 1:visited[next_x][next_y] Trueque.append([next_x, next_y])area 1return flag, area
res 0for i in range(n):for j in range(m):if matrix[i][j] 1 and not visited[i][j]:visited[i][j] Trueflag, area bfs(matrix, visited, i, j)if not flag:res area# if bfs(matrix, visited, i, j) 1:# res 1
print(res)102. 沉没孤岛
卡码网 102. 沉没孤岛 代码随想录
from collections import deque
n, m map(int, input().split())matrix []for i in range(n):matrix.append(list(map(int, input().split())))visited [[False] * m for _ in range(n)]directions [[1,0],[-1,0],[0,-1],[0,1]]def bfs(matrix, visited, x, y):area 1que deque([])que.append([x,y])flag Falseback_up deque([])while que:# 弹出一个点cur_x, cur_y que.popleft()# 把遍历的所有点就记录下来如果确定是一个孤岛把这些左边置为0back_up.append([cur_x, cur_y])if cur_x 0 or cur_x len(matrix)-1 or cur_y 0 or cur_y len(matrix[0])-1:flag True# 四个方向遍历四个方向for i, j in directions:next_x cur_x inext_y cur_y jif next_x 0 or next_x len(matrix) or next_y 0 or next_y len(matrix[0]):continueif not visited[next_x][next_y] and matrix[next_x][next_y] 1:visited[next_x][next_y] Trueque.append([next_x, next_y])area 1if not flag:while back_up:cur_x, cur_y back_up.popleft()matrix[cur_x][cur_y] 0# return flag, area
res 0for i in range(n):for j in range(m):if matrix[i][j] 1 and not visited[i][j]:visited[i][j] Truebfs(matrix, visited, i, j)
# print(res)
for i in range(len(matrix)):# print( .jion(map(str, matrix[i])))print( .join([str(item) for item in matrix[i]]).strip())103. 水流问题
卡码网 103. 水流问题 代码随想录
from collections import deque
n, m map(int, input().split())matrix []for i in range(n):matrix.append(list(map(int, input().split())))visited [[False] * m for _ in range(n)]directions [[1,0],[-1,0],[0,-1],[0,1]]first set()
second set()def dfs(matrix, visited, x, y, node):if visited[x][y]:returnnode.add((x,y))visited[x][y] Truefor i, j in directions:next_x x inext_y y jif (0 next_x len(matrix) and 0 next_y len(matrix[0]) and matrix[next_x][next_y] matrix[x][y]):dfs(matrix, visited, next_x, next_y, node)# 右/上
for i in range(len(matrix)):dfs(matrix, visited, i, 0, first)
for j in range(len(matrix[0])):dfs(matrix, visited, 0, j, first)
# print(first)# visited需要重新初始化
visited [[False] * m for _ in range(n)]
for i in range(len(matrix)):dfs(matrix, visited, i, len(matrix[0])-1, second)
for j in range(len(matrix[0])):dfs(matrix, visited, len(matrix)-1, j, second)
# print(second)res first second
# print(res)for x,y in res:print(f{x} {y})104.建造最大岛屿
卡码网 104.建造最大岛屿 代码随想录
from collections import deque
n,m map(int, input().split())matrix []for i in range(n):matrix.append(list(map(int, input().split())))
# 记录遍历
visited [[False]*m for _ in range(n)]
# 记录岛屿编号
marked [[0]*m for i in range(n)]directions [[-1,0],[1,0],[0,-1],[0,1]]def bfs(matrix, visited, x, y, marked, isoland_cnt):area 1que deque([])que.append([x,y])# 记录新的岛屿marked[x][y] isoland_cntwhile que:cur_x, cur_y que.popleft()for i, j in directions:next_x cur_x inext_y cur_y jif next_x 0 or next_x len(matrix) or next_y 0 or next_y len(matrix[0]):continueif not visited[next_x][next_y] and matrix[next_x][next_y] 1:visited[next_x][next_y] Truemarked[next_x][next_y] isoland_cntque.append([next_x, next_y])area 1return areaisoland_cnt 1
area_dict dict()
for i in range(n):for j in range(m):if matrix[i][j] 1 and not visited[i][j]:visited[i][j] Truearea bfs(matrix, visited, i, j, marked, isoland_cnt)area_dict[isoland_cnt] areaisoland_cnt 1res 0
# 开始填充
for i in range(n):for j in range(m):if marked[i][j] 0:max_area 1isoland_set set()for x,y in directions:next_x x inext_y y jif (0 next_x n and 0 next_y m and marked[next_x][next_y] ! 0 and marked[next_x][next_y] not in isoland_set):max_area area_dict[marked[next_x][next_y]]isoland_set.add(marked[next_x][next_y])res max(max_area, res)
if res 0:print(n*m)
else:print(res)
