代码随想录D52-53 图论 Python
目录
101. 孤岛的总面积
102. 沉没孤岛
103. 水流问题
104. 建造最大岛屿
101. 孤岛的总面积
要点：
整体来说是一个图着色的问题。
这道题目的思路符合直觉，但代码实现会和直觉有差别。如果仅使用visit记录不使用着色，会遇到非常多的判断问题。
最好的解决方案是对边缘进行判断，然后先将所有挨着岸边的岛屿着色成海洋，随后重新初始化面积计数，对中央的孤岛面积进行计算。
实现1 深度优先遍历：
direct = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(grid, x, y):
global count
## 凡遇到节点即着色
count += 1
grid[x][y] = 0
for i, j in direct:
n_x, n_y = x + i, y + j
if 0 <= n_x < len(grid) and 0 <= n_y < len(grid[0]) and grid[n_x][n_y] == 1:
dfs(grid, n_x, n_y)
def main():
global count
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
count = 0
## 清除左右边界
for i in range(n):
## 清除上下边界
for j in range(m):
if i == 0 or j == 0 or i == n-1 or j == m-1:
if grid[i][j]:
dfs(grid, i, j)
## 正式的遍历
count = 0
for i in range(n):
for j in range(m):
if grid[i][j]:
dfs(grid, i, j)
print(count)
if __name__ == '__main__':
main()实现2 广度优先遍历：
from collections import deque
direct = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def bfs(grid, x, y, ):
count = 1
que = deque([])
que.append([x, y])
while que:
cur_x, cur_y = que.popleft()
grid[cur_x][cur_y] = 0
for i, j in direct:
next_x, next_y = cur_x + i, cur_y + j
if next_x < 0 or next_y < 0 or next_x >= len(grid) or next_y >= len(grid[0]):
continue
if grid[next_x][next_y] == 1:
count += 1
grid[next_x][next_y] = 0
que.append([next_x, next_y])
return count
def main():
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
count = 0
for i in range(n):
for j in range(m):
if i == 0 or j == 0 or i == n-1 or j == m-1:
if grid[i][j] == 1:
bfs(grid, i, j, )
# print(grid)
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
cur_count = bfs(grid, i, j, )
count += cur_count
print(count)
if __name__ == '__main__':
main()102. 沉没孤岛
要点：
同样是图着色问题，但是要着色的区域和上一题刚好相反。
由于要输出变化后的矩阵，那么就按照之前的方法先将边缘位置全部变为2，最后做一次转换即可。
实现1 广度优先搜索：
使用一个自定义标记，很快就能够完成了
from collections import deque
direct = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def bfs(grid, x, y, l = 2):
count = 1
que = deque([])
que.append([x, y])
grid[x][y] = l
while que:
cur_x, cur_y = que.popleft()
for i, j in direct:
next_x, next_y = cur_x + i, cur_y + j
if next_x < 0 or next_y < 0 or next_x >= len(grid) or next_y >= len(grid[0]):
continue
if grid[next_x][next_y] == 1:
grid[next_x][next_y] = l
que.append([next_x, next_y])
count += 1
return count
def main():
count = 0
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
for j in range(m):
if i == 0 or j == 0 or i == n-1 or j == m-1:
if grid[i][j] == 1:
bfs(grid, i, j)
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
count += bfs(grid, i, j, l = 0)
for i in range(n):
for j in range(m):
if grid[i][j] == 2:
grid[i][j] = 1
print(' '.join(map(str, grid[i])))
if __name__ == '__main__':
main()
实现2 深度优先遍历：
本题主要就是在做着色，不需要计数。
direct = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(grid, x, y, l = 0):
grid[x][y] = l
for i, j in direct:
next_x, next_y = x + i, y + j
if next_x < 0 or next_y < 0 or next_x >= len(grid) or next_y >= len(grid[0]):
continue
if grid[next_x][next_y] == 0 or grid[next_x][next_y] == 2:
continue
dfs(grid, next_x, next_y, l)
def main():
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
for j in range(m):
if i == 0 or j == 0 or i == n-1 or j == m-1:
if grid[i][j] == 1:
dfs(grid, i, j, 2)
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
dfs(grid, i, j)
for i in range(n):
for j in range(m):
if grid[i][j] == 2:
grid[i][j] = 1
print(' '.join(map(str, grid[i])))103. 水流问题
要点：
如果是用暴力解法，就是从每个节点进行搜索，最后记录并输出结果。
如果逆向思考，使用着色的思想，从两个边界出发，对整张图进行着色，附上不同的颜色，最终输出这些位置。就可以实现只遍历一次边框位置。
实现：
first = set()
second = set()
directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
def dfs(i, j, graph, visited, side):
if visited[i][j]:
return
visited[i][j] = True
side.add((i, j))
for x, y in directions:
new_x = i + x
new_y = j + y
if (
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 first
global second
N, 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 & second
for x, y in res:
print(f"{x} {y}")
if __name__ == "__main__":
main()104. 建造最大岛屿
要点：
读完题目发现难点是确定应该将陆地建造在哪里。如果每个位置都做一次搜索，时间肯定会慢。
这里可以使用字典的方式，使用defaultdict记录一下每个岛的id，坐标，面积。然后再对每个位置上建造陆地能带来的最大面积做计算即可。
具体来说，建立defaultdict来记录每个岛屿id的面积，每个grid着色成岛屿id。最终统计每个节点周围岛屿id对应的面积之和。
实现：
from collections import defaultdict
direct = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def count_ones(grid):
return sum(row.count(1) for row in grid)
def dfs(grid, visit, x, y, idx):
global area
if visit[x][y]:
return
visit[x][y] = True
grid[x][y] = idx
area += 1
for i, j in direct:
next_x, next_y = x + i, y + j
if 0 <= next_x < len(grid) and 0 <= next_y < len(grid[0]) and grid[next_x][next_y] == 1:
dfs(grid, visit, next_x, next_y, idx)
def main():
global area
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
if count_ones(grid) == n * m:
print(count_ones(grid))
return
visit = [[False] * m for _ in range(n)]
island_area = defaultdict()
idx = 2
for i in range(n):
for j in range(m):
if grid[i][j] == 1 and not visit[i][j]:
area = 0
dfs(grid, visit, i, j, idx)
island_area[idx] = area
idx += 1
max_area = 1
for i in range(n):
for j in range(m):
new_island = grid[i][j]
merge_area = 1
idx_set = set()
for x, y in direct:
if 0 <= i + x < len(grid) and 0 <= j + y < len(grid[0]):
idx = grid[i + x][j + y]
if idx not in idx_set:
merge_area += island_area.get(idx, 0)
idx_set.add(idx)
if merge_area > max_area:
max_area = merge_area
print(max_area)
if __name__ == '__main__':
main()