目录
任务
Kama101. 孤岛的总面积
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。
思路
只有孤岛才计算面积，所以先遍历边缘岛，将这些不符合条件的格子遍历并标记后，再遍历孤岛并计算。
# 处理输入
n, m = map(int, input().strip().split())
grid = []
for _ in range(n):
row = list(map(int, input().strip().split()))
grid.append(row)
count = 0
def dfs(grid,visited,x,y):
global count
dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
visited[x][y] = True # 由调用者（包含外部和自身）保证了该格子为访问过的陆地！
count += 1
for i in range(4):
nextX = x + dir[i][0]
nextY = y + dir[i][1]
if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
continue
if visited[nextX][nextY] == False and grid[nextX][nextY] == 1: #未访问过的陆地则继续访问（直到遍历完整个单独的岛屿）
dfs(grid,visited,nextX,nextY)
visited = [[False]*m for _ in range(n)]
# 将边缘岛的所有陆地格子标记为已访问(从边缘开始dfs遍历)
for j in range(m):
if grid[0][j] == 1 and not visited[0][j]:
dfs(grid,visited,0,j)
if grid[n-1][j]==1 and not visited[n-1][j]:
dfs(grid,visited,n-1,j)
for i in range(n):
if grid[i][0] == 1 and not visited[i][0]:
dfs(grid,visited,i,0)
if grid[i][m-1] == 1 and not visited[i][m-1]:
dfs(grid,visited,i,m-1)
#遍历中间格子并累计值
sum = 0
for i in range(1,n-1):
for j in range(1,m-1):
if visited[i][j]==False and grid[i][j] ==1:
count = 0
dfs(grid,visited,i,j)
sum += count
print(sum)
Kama102. 沉没孤岛
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。
思路
同样的，将边缘岛遍历并标记，然后将其他的1变成0，即符合题意（中间的所有1均为孤岛）
# 处理输入
n, m = map(int, input().strip().split())
grid = []
for _ in range(n):
row = list(map(int, input().strip().split()))
grid.append(row)
count = 0
def dfs(grid,visited,x,y):
dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
visited[x][y] = True # 由调用者（包含外部和自身）保证了该格子为访问过的陆地！
for i in range(4):
nextX = x + dir[i][0]
nextY = y + dir[i][1]
if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
continue
if visited[nextX][nextY] == False and grid[nextX][nextY] == 1: #未访问过的陆地则继续访问（直到遍历完整个单独的岛屿）
dfs(grid,visited,nextX,nextY)
visited = [[False]*m for _ in range(n)]
# 将边缘岛的所有陆地格子标记为已访问(从边缘开始dfs遍历)
for j in range(m):
if grid[0][j] == 1 and not visited[0][j]:
dfs(grid,visited,0,j)
if grid[n-1][j]==1 and not visited[n-1][j]:
dfs(grid,visited,n-1,j)
for i in range(n):
if grid[i][0] == 1 and not visited[i][0]:
dfs(grid,visited,i,0)
if grid[i][m-1] == 1 and not visited[i][m-1]:
dfs(grid,visited,i,m-1)
#遍历中间格子并将孤岛修改为水
sum = 0
for i in range(1,n-1):
for j in range(1,m-1):
if visited[i][j]==False and grid[i][j] ==1:
grid[i][j] = 0
for i in range(n):
for j in range(m):
print(grid[i][j],end = ' ')
print()
Kama103. 水流问题
现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。
矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界
思路
以边界为起点，统计所有可以遍历到的节点，如果是第一，第二边界都能统计到的点，为符合题意的点，输出即可。
# 处理输入
n, m = map(int, input().strip().split())
grid = []
for _ in range(n):
row = list(map(int, input().strip().split()))
grid.append(row)
dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
count = 0 # 单个岛屿的面积
def dfs(grid,visited,x,y):
global dir
visited[x][y] = True # 由调用者（包含外部和自身）保证了该格子为访问过的陆地！
for i in range(4):
nextX = x + dir[i][0]
nextY = y + dir[i][1]
if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
continue
if not visited[nextX][nextY] and grid[x][y] <= grid[nextX][nextY]: #从低往高遍历所能达到的所有节点，记录在visited中
dfs(grid,visited,nextX,nextY)
first = [[False]*m for _ in range(n)]
second = [[False]*m for _ in range(n)]
#从边界开始遍历，标记所有遍历过的节点
for j in range(m):
dfs(grid,first,0,j)
dfs(grid,second,n-1,j)
for i in range(n):
dfs(grid,first,i,0)
dfs(grid,second,i,m-1)
mySet = set()
for i in range(n):
for j in range(m):
if first[i][j] and second[i][j]: #如果即能被第一边界遍历到，又能被第二边界遍历到，则满足条件
# print(i,end = ' ')
# print(j,end = ' ')
# print()
print(f"{i} {j}")
Kama104. 建造最大岛屿
给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。
岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。
思路
将某个水格子变为陆地格子后，可能与多个（>=0)原岛屿连接形成新岛屿。对于每个水格子，四方向上判断有无陆地格子，还要判断陆地格子是否属于同一岛屿，不能重复添加，符合条件后，累加岛屿的面积。
使用一个map更方便的进行统计，key为岛屿索引，value为岛屿面积。岛屿索引从2开始（因为给定输入所有陆地格子为1，遍历时需要用这个判断是否为陆地）。每次遍历完一个岛屿,岛屿索引+1。
此外使用一个set来判断水格子周围的陆地格子是否属于同一岛屿（是否已经加过相同岛屿面积）
另外注意别忘记了给定输入全是陆地的特殊情况
实际上这里因为有了岛屿索引，所以不需要visited这个二维列表来记录和判断了，但是为了逻辑的清晰，下面的实际实现还是使用这个变量
# 处理输入
n, m = map(int, input().strip().split())
grid = []
for _ in range(n):
row = list(map(int, input().strip().split()))
grid.append(row)
dir = [(1,0),(0,1),(-1,0),(0,-1)] #逆时针四个方向
count = 0 # 单个岛屿的面积
islandIndex = 2 #因为初始时1表示陆地，所以岛屿编号从2开始
def dfs(grid,visited,x,y):
global count
global islandIndex
global dir
visited[x][y] = True # 由调用者（包含外部和自身）保证了该格子为访问过的陆地！
grid[x][y] = islandIndex
count += 1
for i in range(4):
nextX = x + dir[i][0]
nextY = y + dir[i][1]
if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
continue
if visited[nextX][nextY] == False and grid[nextX][nextY] == 1: #未访问过的陆地则继续访问（直到遍历完整个单独的岛屿）
dfs(grid,visited,nextX,nextY)
visited = [[False]*m for _ in range(n)]
# 记录岛屿索引和对应面积
islandMap = {}
for i in range(n):
for j in range(m):
if not visited[i][j] and grid[i][j] == 1:
count = 0
dfs(grid,visited,i,j)
islandMap[islandIndex] = count
islandIndex += 1
#尝试每次将一个水格子变成陆地
result = 0
isAllLand = True
for i in range(n):
for j in range(m):
nowArea = 1 #连接后的岛屿面积，默认为1表示修改水域后未连接其他岛屿
visitedIsland = set() #保存已访问过的岛屿索引
if grid[i][j] == 0:
isAllLand = False
for k in range(4): #四方向上看有没有陆地
nextX = i + dir[k][0]
nextY = j + dir[k][1]
if nextX < 0 or nextY<0 or nextX>=len(grid) or nextY>=len(grid[0]):
continue
if grid[nextX][nextY] in visitedIsland:
continue
if grid[nextX][nextY] in islandMap:
nowArea += islandMap[grid[nextX][nextY]]
visitedIsland.add(grid[nextX][nextY])
result = max(result,nowArea)
if isAllLand:
print(n*m)
else:
print(result)
心得
dfs中的递归深入条件和bfs中的加入队列的条件都是重点，一般是根据题意要求来进行深搜或广搜，对于要求遍历整个图的问题，我们使用的就是visited来访问哪些还未访问过的节点，而对于更细节的题目，比如岛屿问题，水流问题等，深入（或广度）遍历的条件还要加上题目的需求（比如是否是陆地，是否往高处等），此外还要注意从外部初次进入到dfs或bfs的初始情况，比如岛屿问题初次进入时也是必须以陆地格子为起点等。
标签：图论,岛屿,第十二章,range,Part3,grid,visited,nextX,nextY From： https://www.cnblogs.com/haohaoscnblogs/p/18400019