211、【图论】建造最大岛屿（Python）

题目

思路

1. 将每个岛屿分编号，并且对每个编号的岛屿记录面积
2. 尝试在0处添加岛屿，并且判定周围是否有可连接的岛屿计算面积。

代码实现

import collections

directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

def bfs(i, j, num, area):
    graph[i][j] = num
    visited[i][j] = True
    deque = collections.deque()
    deque.append([i, j])
    area += 1

    while deque:
        x, y = deque.popleft()
        for direction in directions:
            next_x, next_y = direction[0], direction[1]
            move_x, move_y = x + next_x, y + next_y
            if move_x < 0 or move_x >= n or move_y < 0 or move_y >= m:
                continue
            if graph[move_x][move_y] == 1 and not visited[move_x][move_y]:
                graph[move_x][move_y] = num
                deque.append([move_x, move_y])
                area += 1

    return area

n, m = list(map(int, input().split()))
graph = []
visited = [[False] * m for _ in range(n)]
for i in range(n):
    graph.append(list(map(int, input().split())))
record_area = collections.defaultdict(int)		# 记录每个编号岛屿的面积

num = 2					# 编号
is_all_grid = True		# 判定是否图中全为岛屿
# 给每个岛屿起编号，并且统计每个编号的面积
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            is_all_grid = False
        if graph[i][j] == 1:
            area = bfs(i, j, num, 0)
            record_area[num] = area            
            num += 1
# 如果全部为岛屿，则直接输出面积
if is_all_grid:
    print(n * m)
# 如果有海，则计算添加岛屿后的连接情况
else:
    res = 0						# 统计面积
    visited_graph = set()		# 让连接的岛屿不被重复统计
    for i in range(n):
        for j in range(m):
            count = 1				# 第一块0被变做岛屿
            visited_graph.clear()	# 每次清空
            if graph[i][j] == 0:            
                for direction in directions:
                    next_x, next_y = i + direction[0], j + direction[1]
                    # 保证不越界、四周探索到的为岛屿并且没有被统计过
                    if (
                        0 <= next_x < n and
                        0 <= next_y < m and 
                        graph[next_x][next_y] != 0 and 
                        graph[next_x][next_y] not in visited_graph                    
                    ):
                    	# 获取岛屿编号，连接岛屿计算面积，访问记录
                        num = graph[next_x][next_y]
                        count += record_area[num]                          
                        visited_graph.add(num)        
            # 每行后统计新情况
            res = max(res, count)

    print(res)

参考文章：建造最大岛屿