目录
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] = 0for 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 countn, 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 = 0for 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 dequedirect = [[1, 0], [0, 1], [-1, 0], [0, -1]]def bfs(grid, x, y, ):count = 1que = deque([])que.append([x, y])while que:cur_x, cur_y = que.popleft()grid[cur_x][cur_y] = 0for 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]):continueif grid[next_x][next_y] == 1:count += 1grid[next_x][next_y] = 0que.append([next_x, next_y])return countdef main():n, m = map(int, input().split())grid = [list(map(int, input().split())) for _ in range(n)]count = 0for 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_countprint(count)if __name__ == '__main__':main()102. 沉没孤岛
要点：
同样是图着色问题，但是要着色的区域和上一题刚好相反。
由于要输出变化后的矩阵，那么就按照之前的方法先将边缘位置全部变为2，最后做一次转换即可。
实现1 广度优先搜索：
使用一个自定义标记，很快就能够完成了
from collections import dequedirect = [[1, 0], [0, 1], [-1, 0], [0, -1]]def bfs(grid, x, y, l = 2):count = 1que = deque([])que.append([x, y])grid[x][y] = lwhile 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]):continueif grid[next_x][next_y] == 1:grid[next_x][next_y] = lque.append([next_x, next_y])count += 1return countdef main():count = 0n, 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] = 1print(' '.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] = lfor 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:continuedfs(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] = 1print(' '.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]:returnvisited[i][j] = Trueside.add((i, j))for x, y in directions:new_x = i + xnew_y = j + yif (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 firstglobal secondN, 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 & secondfor x, y in res:print(f"{x} {y}")if __name__ == "__main__":main()104. 建造最大岛屿
要点：
读完题目发现难点是确定应该将陆地建造在哪里。如果每个位置都做一次搜索，时间肯定会慢。
这里可以使用字典的方式，使用defaultdict记录一下每个岛的id，坐标，面积。然后再对每个位置上建造陆地能带来的最大面积做计算即可。
具体来说，建立defaultdict来记录每个岛屿id的面积，每个grid着色成岛屿id。最终统计每个节点周围岛屿id对应的面积之和。
实现：
from collections import defaultdictdirect = [[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 areaif visit[x][y]:returnvisit[x][y] = Truegrid[x][y] = idxarea += 1for 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 arean, 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))returnvisit = [[False] * m for _ in range(n)]island_area = defaultdict()idx = 2for i in range(n):for j in range(m):if grid[i][j] == 1 and not visit[i][j]:area = 0dfs(grid, visit, i, j, idx)island_area[idx] = areaidx += 1 max_area = 1for i in range(n):for j in range(m):new_island = grid[i][j]merge_area = 1idx_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_areaprint(max_area)if __name__ == '__main__':main()
