代码随想录算法训练营第五十二天 | 101.孤岛的总面积 102.沉没孤岛 103.水流问题 104.建造最大岛屿
101.孤岛的总面积：
思路
分析题目可知，孤岛要求岛屿不能接触边缘，因此总体思路是先从周围遍历，将周围能接触到的陆地打标记，然后再按照之前的方法，遍历求岛屿的面积，即孤岛的面积之和即可。
打标记
打标记的方法有两种，1是周围遍历时，将能访问到的陆地的visited设置为True，2是将能访问到的陆地设置为海水。
深搜
因为main函数中要先遍历周围，再按之前的方法遍历，所以如果dfs还是处理下一个节点的话，那么main函数中要多出四个进入dfs前的处理，不如将dfs改为处理当前节点，即count += 1和打标记，然后先判断节点是否合法，再dfs
其中从周围访问和按之前的方法遍历的dfs函数是同一个，只需要在按之前的方法遍历dfs前设置count=0即可
"""
设置为海水
"""
count = 0
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(grid, x, y):
global count# 容易忘记
count += 1
grid[x][y] = 0 # 设置为海水
for i in range(4):
nextx, nexty = x + direction[i][0], y + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]): # 越界
continue
if grid[nextx][nexty]:
dfs(grid, nextx, nexty)
def main():
global count
n,m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
# 将四周能接触到的陆地设置为海水
for i in range(n): # 第0列和最后一列
if grid[i][0]:
dfs(grid, i, 0)
if grid[i][m - 1]:
dfs(grid, i, m - 1)
for j in range(m): # 第0行和最后一列
if grid[0][j]:
dfs(grid, 0, j)
if grid[n - 1][j]:
dfs(grid, n - 1, j)
count = 0 # 重置count
for x in range(1, n):
for y in range(1, m):
if grid[x][y]: # dfs处理的是下一个节点，所以要处理(x, y)
dfs(grid, x, y)
print(count)
if __name__ == '__main__':
main()
"""
visited设置为True
"""
count = 0
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(grid, visited, x, y):
global count
count += 1
visited[x][y] = True # 设置为已访问过
#print('x: ' + str(x) + 'y: ' + str(y) + 'count: ' + str(count))
for i in range(4):
nextx, nexty = x + direction[i][0], y + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]): # 越界
continue
if not visited[nextx][nexty] and grid[nextx][nexty]:
dfs(grid,visited, nextx, nexty)
def main():
global count
n,m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
visited = [[False] * m for _ in range(n)]
# 将四周能接触到的陆地设置为海水
for i in range(n): # 第0列和最后一列
if not visited[i][0] and grid[i][0]:
dfs(grid,visited, i, 0)
if not visited[i][m - 1] and grid[i][m - 1]:
dfs(grid,visited, i, m - 1)
for j in range(m): # 第0行和最后一列
if not visited[0][j] and grid[0][j]:
dfs(grid,visited, 0, j)
if not visited[n - 1][j] and grid[n - 1][j]:
dfs(grid,visited, n - 1, j)
count = 0 # 重置count
for x in range(1, n):
for y in range(1, m):
if not visited[x][y] and grid[x][y]: # dfs处理的是下一个节点，所以要处理(x, y)
dfs(grid,visited, x, y)
print(count)
if __name__ == '__main__':
main()
广搜
广搜也可以用设置visited或者将访问到的陆地设置为海水的方式。
以设置为海水的方式为例，同样为了避免main函数中增加4个进入bfs函数前的处理，进入bfs函数后，会先对当前节点进行处理：count = 1， 设置为海水，进队列
"""
设置为海水
"""
from collections import deque
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def bfs(grid, x, y):
count = 1 # 记录当前岛屿的面积
grid[x][y] = 0 # 没有用visited，而是将当前节点设置为海水来表明已经遍历过
que = deque()
que.append([x, y])
#if x == 0 or y == 0 or x == len(grid) - 1 or y == len(grid[0]) - 1:
# print("周围")
#else:
# print("x: " + str(x) + "y: " + str(y))
while len(que) != 0:
curx, cury = que.popleft()
#print("curx: " + str(curx) + "cury: " + str(cury) + "count: " + str(count))
for i in range(4):
nextx, nexty = curx + direction[i][0], cury + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]): # 越界
continue
if grid[nextx][nexty]:
count += 1
grid[nextx][nexty] = 0# 准备进队列的节点设置为海水
#print("nextx: " + str(nextx) + "nexty: " + str(nexty) + "count: " + str(count))
que.append([nextx, nexty])
#print("count: " + str(count))
return count
def main():
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
# 把四周能接触到的陆地设置为海水
for i in range(n):
if grid[i][0]:
bfs(grid, i, 0)
if grid[i][m - 1]:
bfs(grid, i, m - 1)
for j in range(m):
if grid[0][j]:
bfs(grid, 0, j)
if grid[n - 1][j]:
bfs(grid, n - 1, j)
result = 0 # 记录孤岛面积
for x in range(1, n):
for y in range(1, m):
if grid[x][y]:
result += bfs(grid, x, y)
print(result)
if __name__ == '__main__':
main()
102.沉没孤岛：
思路
本题与上题相似，只不过本题是要沉没孤岛，而上题要计算孤岛的总面积，那么思路还是一样，先从周围遍历，给能访问到的陆地打标记，然后遍历矩阵，因为本题只需要将孤岛沉没而不需要计算孤岛面积，所以遍历矩阵时不需要进行dfs/bfs访问能接触到的陆地（如果要访问，那需要和周围的bfs/dfs分开），因此遍历矩阵时，遇到1转换为0，遇到打标记的陆地，转换为1
打标记可以就在grid上面操作，bfs/dfs过程中将其设置为与1和0无关的数即可
深搜
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(grid, x, y):
#print("x: " + str(x) + "y: " + str(y))
grid[x][y] = 2 # 周围接触到的陆地打标记
for i in range(4):
nextx, nexty = x + direction[i][0], y + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]): # 越界
continue
if grid[nextx][nexty] == 1: # 是没有打过标记的陆地
dfs(grid, nextx, nexty)
def main():
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
# 给周围接触到的陆地打标记
for i in range(n): # 第0列和最后一列
if grid[i][0] == 1: # 注意这里是判断是否等于1，而不是就是grid[i][0]
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)
# 只需要遍历矩阵，遇到1变为0，遇到2转换为1
for x in range(n):
for y in range(m):
if grid[x][y] == 1:
grid[x][y] = 0
elif grid[x][y] == 2:
grid[x][y] = 1
# 打印
for row in grid:
print(' '.join(map(str, row)))
if __name__ == '__main__':
main()
广搜
from collections import deque
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def bfs(grid, x, y):
grid[x][y] = 2
que = deque()
que.append([x, y])
while len(que) != 0:
curx, cury = que.popleft()
for i in range(4):
nextx, nexty = curx + direction[i][0], cury + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
continue
if grid[nextx][nexty] == 1:
grid[nextx][nexty] = 2
que.append([nextx, nexty])
def main():
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
# 给周围接触到的陆地打标记
for i in range(n): # 第0列和最后一列
if grid[i][0] == 1: # 注意这里是判断是否等于1，而不是就是grid[i][0]
bfs(grid, i, 0)
if grid[i][m - 1] == 1:
bfs(grid, i, m - 1)
for j in range(m):
if grid[0][j] == 1:
bfs(grid, 0, j)
if grid[n - 1][j] == 1:
bfs(grid, n - 1, j)
# 只需要遍历矩阵，遇到1变为0，遇到2转换为1
for x in range(n):
for y in range(m):
if grid[x][y] == 1:
grid[x][y] = 0
elif grid[x][y] == 2:
grid[x][y] = 1
# 打印
for row in grid:
print(' '.join(map(str, row)))
if __name__ == '__main__':
main()
103.水流问题：
思路
首先分析题目，矩阵模拟地形，水从高处往低处/等高处流，要求输出单元格的水能到达第一边界和第二边界的坐标。
暴力
最开始的思路就是，遍历矩阵，然后矩阵中的每个单元格进行一次深搜 / 广搜，visited标记能到达的位置，然后判断能到达的位置中是否同时包含第一边界和第二边界的单元格
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(grid, visited, x, y):
if visited[x][y]:
return
visited[x][y] = True
for i in range(4):
nextx, nexty = x + direction[i][0], y + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
continue
if grid[nextx][nexty] <= grid[x][y]:#从高流向低/等高
dfs(grid, visited, nextx, nexty)
def isResult(grid, x, y):
visited = [[False] * len(grid[0]) for _ in range(len(grid))]# 标记(x, y)能访问到的节点
dfs(grid, visited, x, y)
isFirst, isSecond = False, False
# 第一边界的上边
for j in range(m):
if visited[0][j] == True:
isFirst = True
break
# 第一边界的左边
for i in range(n):
if visited[i][0] == True:
isFirst = True
break
# 第二边界的下边
for j in range(m):
if visited[n - 1][j] == True:
isSecond = True
break
# 第二边界的右边
for i in range(n):
if visited[i][m - 1] == True:
isSecond = True
break
return (isFirst and isSecond)
def main():
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
for i in range(n):
for j in range(m):
if isResult(grid, i, j):
print(str(i) + ' ' + str(j))
if __name__ == '__main__':
main()
分析暴力的时间复杂度，遍历一遍矩阵：n*m，对于矩阵中的每个单元格，都要进行一遍dfs操作：n * m，因此时间复杂度为O(n^2 * m ^ 2)，会超时
优化
从边界的单元格进行逆流 dfs遍历，两个边界都能逆流遍历到的单元格就是所要求的单元格
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def dfs(grid, visited, x, y):
if visited[x][y]:
return
visited[x][y] = True
for i in range(4):
nextx, nexty = x + direction[i][0], y + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
continue
if grid[nextx][nexty] >= grid[x][y]: # 逆流
dfs(grid, visited, nextx, nexty)
def main():
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
firstBorder = [[False] * m for _ in range(n)]
secondBorder = [[False] * m for _ in range(n)]
# 上下边
for j in range(m):
dfs(grid, firstBorder, 0, j) # 边界1
dfs(grid, secondBorder, n - 1, j) # 边界2
# 左右边
for i in range(n):
dfs(grid, firstBorder, i, 0) # 边界1
dfs(grid, secondBorder, i, m - 1) # 边界2
# 求边界1和边界2逆流能到的节点的交集
for i in range(n):
for j in range(m):
if firstBorder[i][j] and secondBorder[i][j]:
print(str(i) + ' ' + str(j))
return
if __name__ == '__main__':
main()
优化的时间复杂度，首先前面两个边界的遍历，isFirst和isSecond中的值最多只遍历一次，因此为2mn，再后面遍历矩阵求交集mn，因此时间复杂度为O(mn)
104.建造最大岛屿：
思路
首先分析题目，最多将一块海水转换为陆地，求建造得到的最大岛屿面积。
而可能出现的情况：1.全是陆地， 2. 海水转换为陆地后将两块岛屿连起来了。如下图所示
暴力
暴力的思路是遍历矩阵，将1块海水转换为陆地后求得到的岛屿的面积。遍历矩阵是mn，对矩阵中的每个单元格，都要经历一次深搜/广搜（原来是陆地的要求一次，原来是海水的转换为陆地求一次），为mn，因此总的时间复杂度为O(n^2 * m^2)
优化
其实只需要一次深搜，对各个岛屿进行标记，并保存标记和对应的岛屿的面积。
然后再遍历一次矩阵，将海水转换为陆地，对其单元格接触到的上下左右的不重复的岛屿面积进行求和，最终得到最大面积。
上下左右有重复的岛屿的如下图
需要注意的是，全是陆地的情况需要独立出来
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
area = 0
def dfs(grid, visited, x, y, mark):
global area
if visited[x][y] or grid[x][y] == 0:
return
visited[x][y] = True
area += 1
grid[x][y] = mark # 打标记
for i in range(4):
nextx, nexty = x + direction[i][0], y + direction[i][1]
if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
continue
dfs(grid, visited, nextx, nexty, mark)
def main():
global area
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
areas = [0, 0] # 记录岛屿编号和对应面积
mark = 2 # 从2开始
visited = [[False] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if not visited[i][j] and grid[i][j] == 1:
area = 0
dfs(grid, visited, i, j, mark)
# areat = area
areas.append(area)
mark += 1
# 遍历矩阵，将海水转换为陆地求最大面积
result = 0
for x in range(n):
for y in range(m):
island = 1 # 面积
vi = set() # 记录遍历过的岛屿
if grid[x][y] == 0:
for i in range(4):
nextx, nexty = x + direction[i][0], y + direction[i][1]
if nextx < 0 or nextx >= n or nexty < 0 or nexty >= m:
continue
if grid[nextx][nexty] not in vi: # 该岛屿没有被访问过
island += areas[grid[nextx][nexty]]
vi.add(grid[nextx][nexty]) # 将编号加入set中，标记已访问过
result = max(result, island)
if result == 0: # 全是陆地
print(n*m)
return 0
print(result)
if __name__ == '__main__':
main()
学习收获：
注意细节和知道总体思路
- 孤岛的总面积，先从周围出发，深搜/广搜把边缘的岛屿设置为0进行沉没，最后再一次深搜得到的就是孤岛的面积，然后进行加和即可
- 沉没孤岛，与上题思路相同，深搜 / 广搜给边缘的岛屿打标记，最后把孤岛设置为0沉没
- 水流问题，优化在于从周围进行逆流，最后求两个边界逆流到的单元格的交集
- 建造最大岛屿，优化在于，一次深搜对不同岛屿打上不同标记， 同时保存标记和对应岛屿的面积关系，最后再将海水转换为陆地，求其上下左右能接触到的不重复的岛屿面积总和，最后求最大值
原文地址：https://blog.csdn.net/decode12/article/details/145242599
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！