代码随想录算法营Day57 ｜ 孤岛的总面积，淹没孤岛，水流题目，制作最大岛屿

孤岛的总面积

这道题先将靠近边界限上的岛屿都放置为0，然后再用深度大概广度搜刮算法去盘算剩余的孤岛总面积

2. count = 0
3. position = [[1, 0], [0, 1], [-1, 0], [0, -1]]
4. def dfs(matrix,x,y):
5.     global count
6.     matrix[x][y] = 0
7.     count += 1
8.     for i,j in position:
9.         next_x = x + i
10.         next_y = y + j
11.         if next_x < 0 or next_y < 0 or next_x >= len(matrix) or next_y >= len(matrix[0]):
12.             continue
13.         if matrix[next_x][next_y] == 1:
14.             dfs(matrix,next_x,next_y)
15.    
16. N,M = map(int,input().split())
17. matrix = []
18. for _ in range(N):
19.     matrix.append(list(map(int,input().split())))
21. for i in range(N):
22.     if matrix[i][0] == 1:
23.         dfs(matrix,i,0)
24.     if matrix[i][M-1] == 1:
25.         dfs(matrix,i,M-1)
26.    
27. for j in range(M):
28.     if matrix[0][j] == 1:
29.         dfs(matrix,0,j)
30.     if matrix[N-1][j] == 1:
31.         dfs(matrix,N-1,j)
32. count=0
33. for i in range(N):
34.     for j in range(M):
35.         if matrix[i][j] == 1:
36.             dfs(matrix,i,j)
37. print(count)

复制代码

淹没孤岛

这道题思绪和上面一样，不外这里必要将边界上的岛屿酿成2。那么此时矩阵当中就只有靠近边界上的2以及孤岛1。这时间只必要将全部数值为2大概为1的都减去1即可。

2. position = [[1, 0], [0, 1], [-1, 0], [0, -1]]
3. def dfs(matrix,x,y):
4.     matrix[x][y] = 2
5.     for i,j in position:
6.         next_x = x + i
7.         next_y = y + j
8.         if next_x < 0 or next_y < 0 or next_x >= len(matrix) or next_y >= len(matrix[0]):
9.             continue
10.         if matrix[next_x][next_y] == 1:
11.             dfs(matrix,next_x,next_y)
12.    
13. N,M = map(int,input().split())
14. matrix = []
15. for _ in range(N):
16.     matrix.append(list(map(int,input().split())))
18. for i in range(N):
19.     if matrix[i][0] == 1:
20.         dfs(matrix,i,0)
21.     if matrix[i][M-1] == 1:
22.         dfs(matrix,i,M-1)
23.    
24. for j in range(M):
25.     if matrix[0][j] == 1:
26.         dfs(matrix,0,j)
27.     if matrix[N-1][j] == 1:
28.         dfs(matrix,N-1,j)
29. count=0
30. for i in range(N):
31.     for j in range(M):
32.         if matrix[i][j] == 1 or matrix[i][j] == 2:
33.             matrix[i][j] -= 1
34.             
35. for l in matrix:
36.     print(" ".join(map(str,l)))

复制代码

水流题目

现有一个 N × M 的矩阵，每个单元格包罗一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被以为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。
矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处活动，但只能从较高或等高的所在流向较低或等高而且相邻（上下左右方向）的所在。我们的目标是确定那些单元格，从这些单元格出发的水可以到达第一组边界和第二组边界。

这道题我们从各边界逆着往内去找可达的路径，然后取这两个可达路径的交集即可。

2. N,M = map(int,input().split())
3. matrix = []
4. for _ in range(N):
5.     matrix.append(list(map(int,input().split())))
7. first = set()
8. second = set()
9. directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
11. def dfs(i,j,grid,visited,side):
12.     if visited[i][j]:
13.         return
14.     visited[i][j] = True
15.     side.add((i,j))
16.     for x,y in directions:
17.         new_x = x + i
18.         new_y = y + j
19.         if 0<= new_x < N and 0<= new_y < M and grid[i][j] <= grid[new_x][new_y]:
20.             dfs(new_x,new_y,grid,visited,side)
22. visited = [[False] * M for _ in range(N)]
23. for i in range(N):
24.     dfs(i,0,matrix,visited,first)
25. for j in range(M):
26.     dfs(0,j,matrix,visited,first)
28. visited = [[False] * M for _ in range(N)]
29. for i in range(N):
30.     dfs(i,M-1,matrix,visited,second)
31. for j in range(M):
32.     dfs(N-1,j,matrix,visited,second)
34. res = first & second
36. for x,y in res:
37.     print(f"{x} {y}")

复制代码

制作最大岛屿

这道题先将各个岛用差别的数字标示出来，并盘算每个岛的面积，而后遍历每个海水记载可以由该海水块毗连起来的陆地的最大面积。

2. N,M = map(int,input().split())
3. matrix = []
4. for _ in range(N):
5.     matrix.append(list(map(int,input().split())))
7. directions = [[-1, 0], [0, 1], [0, -1], [1, 0]]
8. area = 0
10. def dfs(i,j,grid,visited,num):
11.     global area
13.     if visited[i][j]:
14.         return
15.    
16.     visited[i][j] = True
17.     grid[i][j] = num
18.     area += 1
19.     for x, y in directions:
20.         new_x = x + i
21.         new_y = y + j
22.         if 0 <= new_x < N and 0 <= new_y < M and grid[new_x][new_y] == 1:
23.             dfs(new_x,new_y,grid,visited,num)
25. cnt = 2
26. visited = [[False] * M for _ in range(N)]
27. rec = {}
28. for i in range(N):
29.     for j in range(M):
30.         if matrix[i][j] == 1:
31.             area = 0
32.             dfs(i,j,matrix,visited,cnt)
33.             rec[cnt] = area
34.             cnt += 1
36. res = 0
37. for i in range(N):
38.     for j in range(M):
39.         if matrix[i][j] == 0:
40.             max_island = 1
41.             v = set()
42.             for x, y in directions:
43.                 new_x = x + i
44.                 new_y = y + j
45.                 if 0 <= new_x < N and 0 <= new_y < M and matrix[new_x][new_y] != 0 and matrix[new_x][new_y] not in v:
46.                     max_island += rec[matrix[new_x][new_y]]
47.                     v.add(matrix[new_x][new_y])
48.             res = max(res,max_island)
49. if res == 0:
50.     print(max(rec.values()))
51. else:
52.     print(res)

复制代码