【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104

【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104

需强化知识点

• 103，104 优化思路

题目

101. 孤岛的总面积

• 此处 area 多余

def dfs(grid, x, y, area):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]m, n = len(grid), len(grid[0])area[0] += 1grid[x][y] = 0for add_x, add_y in dirs:next_x, next_y = x + add_x, y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y]:dfs(grid, next_x, next_y, area)tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]
grid = [[0] * n for _ in range(m)]for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]for i in range(m):if grid[i][0]:dfs(grid, i, 0, [0])if grid[i][n-1]:dfs(grid, i, n-1, [0])for j in range(n):if grid[0][j]:dfs(grid, 0, j, [0])if grid[m-1][j]:dfs(grid, m-1, j, [0])cur = 0
for i in range(m):for j in range(n):if grid[i][j]:cur += 1print(cur)          

102. 沉没孤岛

• 思路：从左右上下边界出发遍历，然后visited数组标记，最后 grid 为 1 且没被访问过的，即为孤岛

import collectionsdef bfs(grid, visited, x, y):dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]m, n = len(grid), len(grid[0])que = collections.deque()que.append([x, y])visited[x][y] = Truewhile que:tmp = que.popleft()cur_x, cur_y = tmp[0], tmp[1]for add_x, add_y in dirs:next_x, next_y = cur_x + add_x, cur_y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y] and not visited[next_x][next_y]:que.append([next_x, next_y])visited[next_x][next_y] = Truetmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]
grid = [[0] * n for _ in range(m)]
visited = [[False] * n for _ in range(m)]for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]for i in range(m):if grid[i][0]:bfs(grid, visited ,i, 0)if grid[i][n-1]:bfs(grid, visited, i, n-1)for j in range(n):if grid[0][j]:bfs(grid, visited, 0, j)if grid[m-1][j]:bfs(grid, visited, m-1, j)for i in range(m):for j in range(n):if grid[i][j] and not visited[i][j]:grid[i][j] = 0for i in range(m):for j in range(n):print(grid[i][j], end=" ")

103. 水流问题

• 暴力法：直接每个位置 dfs，然后根据其最终是否能到达边界位置，返回布尔值
• 优化思路：从边界出发，逆流而上，最终不能被访问到的地方为结果

# def dfs(grid, visited, x, y):
#     dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]#     m, n = len(grid), len(grid[0])
#     visited[x][y] = True#     for add_x, add_y in dirs:
#         next_x, next_y = x + add_x, y + add_y
#         if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
#             continue
#         if grid[x][y] < grid[next_x][next_y]:
#             continue
#         if not visited[next_x][next_y]:
#             dfs(grid, visited, next_x, next_y)# def isResult(grid, x, y):
#     m, n = len(grid), len(grid[0])
#     visited = [[False] * n for _ in range(m)]
#     dfs(grid, visited, x, y)
#     first_result, second_result = False, False#     for i in range(m):
#         if visited[i][0]:
#             first_result = True
#         if visited[i][n-1]:
#             second_result = True#     for j in range(n):
#         if visited[0][j]:
#             first_result = True
#         if visited[m-1][j]:
#             second_result = True#     return first_result and second_result# tmp = list(map(int, input().split()))
# m, n = tmp[0], tmp[1]# grid = [[0] * n for _ in range(m)]
# for i in range(m):
#     tmp = list(map(int, input().split()))
#     for j in range(n):
#         grid[i][j] = tmp[j]# for i in range(m):
#     for j in range(n):
#         if isResult(grid, i, j):
#             print("{} {}".format(i, j))def dfs(grid, visited, x, y):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]m, n = len(grid), len(grid[0])visited[x][y] = Truefor add_x, add_y in dirs:next_x, next_y = x + add_x, y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continue# 等于不行if grid[x][y] > grid[next_x][next_y]:continueif not visited[next_x][next_y]:dfs(grid, visited, next_x, next_y)tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]grid = [[0] * n for _ in range(m)]
for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]   visited_first = [[False]*n for _ in range(m)]
visited_second = [[False]*n for _ in range(m)]for i in range(m):dfs(grid, visited_first, i, 0)dfs(grid, visited_second, i, n-1)for j in range(n):dfs(grid, visited_first, 0, j)dfs(grid, visited_second, m-1, j)for i in range(m):for j in range(n):if visited_first[i][j] and visited_second[i][j]:print("{} {}".format(i, j))

104. 建造最大岛屿

• 暴力法：直接每个为0的位置，dfs，记录其面积
• 优化思路：先记录每个岛屿的面积，并编号，然后 每个为0的位置，假设其为1，然后加上周围能访问到岛屿面积
  • 注意周围访问岛屿的去重问题，以及为grid 0的情况

def dfs(grid, mask, x, y, count):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]m, n = len(grid), len(grid[0])grid[x][y] = maskcount[0] += 1for add_x, add_y in dirs:next_x, next_y = x + add_x, y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y] != 1 :continuedfs(grid, mask, next_x, next_y, count)def main():tmp = list(map(int, input().split()))m, n = tmp[0], tmp[1]grid = [[0] * n for _ in range(m)]for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]   mask = 2isAllgrid = TruegridNum = {}for i in range(m):for j in range(n):if grid[i][j] == 0:isAllgrid = Falseif grid[i][j] == 1:count = [0]dfs(grid, mask, i, j, count)gridNum[mask] = count[0]mask += 1if isAllgrid:print(m*n)return result = 0dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]for i in range(m):for j in range(n):if grid[i][j] == 0:tmp = 1visitedGrid = []for add_x, add_y in dirs:next_x, next_y = i + add_x, j + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y] not in visitedGrid and grid[next_x][next_y] != 0:tmp += gridNum[grid[next_x][next_y]]visitedGrid.append(grid[next_x][next_y])result = max(result, tmp)print(result)   main()