- 孤岛的总面积
https://kamacoder.com/problempage.php?pid=1173
代码随想录
https://www.programmercarl.com/kamacoder/0102.沉没孤岛.html
102.沉没孤岛
https://kamacoder.com/problempage.php?pid=1174
代码随想录
https://www.programmercarl.com/kamacoder/0102.沉没孤岛.html
103.水流问题
https://kamacoder.com/problempage.php?pid=1175
代码随想录
https://www.programmercarl.com/kamacoder/0103.水流问题.html
104.建造最大岛屿
https://www.programmercarl.com/kamacoder/0104.建造最大岛屿.html
代码随想录
https://www.programmercarl.com/kamacoder/0104.建造最大岛屿.html
101. 孤岛的总面积
-
孤岛：不和边缘相连的岛屿称为孤岛
-
将所有和边缘相连的岛屿变为平地然后统计孤岛的总面积
深度优先搜索
def dfs(graph,x,y): direction = [[0,-1],[0,1],[1,0],[-1,0]] graph[x][y] = 0 for dir_ in direction: nextx = x+dir_[0] nexty = y+dir_[1] if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]): continue if graph[nextx][nexty]==1: graph[nextx][nexty]=0 dfs(graph,nextx,nexty) def main(): n,m = map(int,input().split()) graph = [[0]*m for _ in range(n)] visited = [[False]*m for _ in range(n)] for i in range(n): data = input().split() for j in range(m): graph[i][j] = int(data[j]) # 将边界所有岛屿变为平地 for i in range(n): if graph[i][0]==1: dfs(graph,i,0) if graph[i][m-1]==1: dfs(graph,i,m-1) for j in range(m): if graph[0][j]==1: dfs(graph,0,j) if graph[n-1][j]==1: dfs(graph,n-1,j) #统计剩余孤岛 res = 0 for i in range(n): for j in range(m): if graph[i][j]==1: res+=1 print(res) if __name__ == '__main__': main()广度优先搜索
def dfs(graph,x,y): direction = [[0,-1],[0,1],[1,0],[-1,0]] graph[x][y] = 0 queue = [[x,y]] while queue: curr = queue.pop() x = curr[0] y = curr[1] graph[x][y] = 0 for dir_ in direction: nextx = x+dir_[0] nexty = y+dir_[1] if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]): continue if graph[nextx][nexty]==1: graph[nextx][nexty] = 0 queue.append([nextx,nexty])
102. 沉没孤岛
-
将不是孤岛的岛变为2
-
最后处理的：2->1 1->0 0->0
深度优先搜索
def dfs(graph,x,y): direction = [[0,-1],[0,1],[1,0],[-1,0]] graph[x][y] = 2 for dir_ in direction: nextx = x+dir_[0] nexty = y+dir_[1] if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]): continue if graph[nextx][nexty]==1: graph[nextx][nexty]=2 dfs(graph,nextx,nexty)广度优先搜索
def dfs(graph,x,y): direction = [[0,-1],[0,1],[1,0],[-1,0]] graph[x][y] = 0 queue = [[x,y]] while queue: curr = queue.pop() x = curr[0] y = curr[1] graph[x][y] = 2 for dir_ in direction: nextx = x+dir_[0] nexty = y+dir_[1] if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]): continue if graph[nextx][nexty]==1: graph[nextx][nexty] = 2 queue.append([nextx,nexty]) def main(): n,m = map(int,input().split()) graph = [[0]*m for _ in range(n)] visited = [[False]*m for _ in range(n)] for i in range(n): data = input().split() for j in range(m): graph[i][j] = int(data[j]) # print(graph) for i in range(n): if graph[i][0]==1: dfs(graph,i,0) if graph[i][m-1]==1: dfs(graph,i,m-1) for j in range(m): if graph[0][j]==1: dfs(graph,0,j) if graph[n-1][j]==1: dfs(graph,n-1,j) res = 0 for i in range(n): for j in range(m): if graph[i][j]==1: graph[i][j] = 0 if graph[i][j] ==2: graph[i][j] = 1 for i in range(n): print(" ".join(map(str,graph[i]))) if __name__ == '__main__': main()
103. 水流问题
-
从两个边界开始向上找重合点；
-
最终把两个边界的重合点作为结果输出；
点击查看代码
def dfs(graph,x,y,bound_res): directions = [[0,-1],[0,1],[1,0],[-1,0]] if not bound_res[x][y]: bound_res[x][y] = True for dir_ in directions: nextx = x+dir_[0] nexty = y+dir_[1] if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]): continue if graph[nextx][nexty]>=graph[x][y] and not bound_res[nextx][nexty]: bound_res[nextx][nexty] = True dfs(graph,nextx,nexty,bound_res) def main(): n,m = map(int,input().split()) graph = [[0]*m for _ in range(n)] for i in range(n): data = input().split() for j in range(m): graph[i][j] = int(data[j]) bound_1 = [[False]*m for _ in range(n)] bound_2 = [[False]*m for _ in range(n)] for i in range(n): dfs(graph,i,0,bound_1) dfs(graph,i,m-1,bound_2) for j in range(m): dfs(graph,0,j,bound_1) dfs(graph,n-1,j,bound_2) for i in range(n): for j in range(m): if bound_1[i][j] and bound_2[i][j]: print(" ".join([str(i),str(j)])) if __name__ == '__main__': main()
104.建造最大岛屿
- 首先分别标记不同岛屿的大小、修改graph上岛屿为index；
- 分别统计水变成陆地后附近岛屿大小和；
点击查看代码
def dfs(graph,visited,x,y,mark,count):
directions = [[0,-1],[0,1],[1,0],[-1,0]]
for dir_ in directions:
nextx = x+dir_[0]
nexty = y+dir_[1]
if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>= len(graph[0]):
continue
if graph[nextx][nexty]==1 and visited[nextx][nexty]==0:
count = count+1
visited[nextx][nexty] = 1
graph[nextx][nexty] = mark
count = dfs(graph,visited,nextx,nexty,mark,count)
return count
def main():
n,m = map(int,input().split())
graph = [[0]*m for _ in range(n)]
for i in range(n):
data = input().split()
for j in range(m):
graph[i][j] = int(data[j])
visited = [[0]*m for _ in range(n)]
map_ = {}
isgrid = True
mark = 2
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
isgrid = False
if visited[i][j]==0 and graph[i][j]==1:
count = 1
visited[i][j] = 1
graph[i][j] = mark
count = dfs(graph,visited,i,j,mark,count)
map_[mark] = count
mark = mark+1
# print(graph)
if isgrid:
print(str(n*m))
return
directions = [[0,-1],[0,1],[1,0],[-1,0]]
res = 0
# visited_grid = []
for i in range(n):
for j in range(m):
count = 1
visited_grid = []
if graph[i][j]==0:
for dir_ in directions:
nextx = i+dir_[0]
nexty = j+dir_[1]
if nextx<0 or nextx>=len(graph) or nexty<0 or nexty>= len(graph[0]):
continue
if graph[nextx][nexty] in visited_grid:
continue
if graph[nextx][nexty]>0:
count+= map_[graph[nextx][nexty]]
visited_grid.append(graph[nextx][nexty])
res = max(res,count)
print(str(res))
if __name__ == '__main__':
main()