代码随想录算法训练营第51天｜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)