101. 孤岛的总面积

direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
result = 0def dfs(grid, y, x):grid[y][x] = 0global resultresult += 1for i, j in direction:next_x = x + jnext_y = y + iif (next_x < 0 or next_y < 0 ornext_x >= len(grid[0]) or next_y >= len(grid)):continueif grid[next_y][next_x] == 1 and not visited[next_y][next_x]:visited[next_y][next_x] = Truedfs(grid, next_y, next_x)n, m = map(int, input().split())
grid = []
visited = [[False] * m for _ in range(n)]for i in range(n):grid.append(list(map(int, input().split())))# 处理边界
for j in range(m):# 上边界if grid[0][j] == 1 and not visited[0][j]:visited[0][j] = Truedfs(grid, 0, j)# 下边界if grid[n - 1][j] == 1 and not visited[n - 1][j]:visited[n - 1][j] = Truedfs(grid, n - 1, j)for i in range(n):# 左边界if grid[i][0] == 1 and not visited[i][0]:visited[i][0] = Truedfs(grid, i, 0)# 右边界if grid[i][m - 1] == 1 and not visited[i][m - 1]:visited[i][m - 1] = Truedfs(grid, i, m - 1)# 计算孤岛总面积
result = 0  # 初始化for i in range(n):for j in range(m):if grid[i][j] == 1 and not visited[i][j]:visited[i][j] = Truedfs(grid, i, j)# 输出孤岛的总面积
print(result)

102. 沉没孤岛

思路：

        从地图周边出发，将周边空格相邻的陆地都做上标记，然后在遍历一遍地图，遇到 陆地 且没做过标记的，那么都是地图中间的 陆地 ，全部改成水域就行。

方法：直接改陆地为其他特殊值作为标记的方式进行；

        步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）

        步骤二：将水域中间 1 （陆地）全部改成 水域（0）

        步骤三：将之前标记的 2 改为 1 （陆地）

def dfs(grid, x, y):grid[x][y] = 2directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]for dx, dy in directions:next_x, next_y = x + dx, y + dy# 超过边界if next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):continueif grid[next_x][next_y] == 0 or grid[next_x][next_y] == 2:continuedfs(grid, next_x, next_y)def main():n, m = map(int, input().split())grid = [[False] * m for _ in range(n)]# 步骤一# 从左侧边，和右侧边，向中间遍历for i in range(n):if grid[i][0] == 1:dfs(grid, i, 0)if grid[i][m-1] == 1:dfs(grid, i, m-1)# 从上边和下边，向中间遍历for j in range(m):if grid[0][j] == 1:dfs(grid, 0, j)if grid[n-1][j] == 1:dfs(grid, n-1, j)# 步骤二、步骤三for i in range(n):for j in range(m):if grid[i][j] == 1:grid[i][j] = 0if grid[i][j] == 2:grid[i][j] == 1# 打印结果for row in grid:print(' '.join(map(str, row)))if __name__ == '__main__':main()

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. 建造最大岛屿

要求：最多可以将矩阵中的一格水变为一块陆地；

思路：遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积；

优化思路：用一次深搜把每个岛屿的面积记录下来就好；

        第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

        第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

 本题没有理解，暂时放一放；

from typing import List
from collections import defaultdictclass Solution:def __init__(self):self.direction = [(1,0),(-1,0),(0,1),(0,-1)]self.res = 0self.count = 0self.idx = 1self.count_area = defaultdict(int)def max_area_island(self, grid: List[List[int]]) -> int:if not grid or len(grid) == 0 or len(grid[0]) == 0:return 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:self.count = 0self.idx += 1self.dfs(grid,i,j)# print(grid)self.check_area(grid)# print(self.count_area)if self.check_largest_connect_island(grid=grid):return self.res + 1return max(self.count_area.values())def dfs(self,grid,row,col):grid[row][col] = self.idxself.count += 1for dr,dc in self.direction:_row = dr + row _col = dc + col if 0<=_row<len(grid) and 0<=_col<len(grid[0]) and grid[_row][_col] == 1:self.dfs(grid,_row,_col)returndef check_area(self,grid):m, n = len(grid), len(grid[0])for row in range(m):for col in range(n):self.count_area[grid[row][col]] = self.count_area.get(grid[row][col],0) + 1returndef check_largest_connect_island(self,grid):m, n = len(grid), len(grid[0])has_connect = Falsefor row in range(m):for col in range(n):if grid[row][col] == 0:has_connect = Truearea = 0visited = set()for dr, dc in self.direction:_row = row + dr _col = col + dcif 0<=_row<len(grid) and 0<=_col<len(grid[0]) and grid[_row][_col] != 0 and grid[_row][_col] not in visited:visited.add(grid[_row][_col])area += self.count_area[grid[_row][_col]]self.res = max(self.res, area)return has_connectdef main():m, n = map(int, input().split())grid = []for i in range(m):grid.append(list(map(int,input().split())))sol = Solution()print(sol.max_area_island(grid))if __name__ == '__main__':main()