99.岛屿数量
https://kamacoder.com/problempage.php?pid=1171
岛屿深搜
https://www.programmercarl.com/kamacoder/0099.岛屿的数量深搜.html
岛屿广搜
https://www.programmercarl.com/kamacoder/0099.岛屿的数量广搜.html#思路
100.岛屿的最大面积
https://www.programmercarl.com/kamacoder/0100.岛屿的最大面积.html
代码随想录
https://www.programmercarl.com/kamacoder/0100.岛屿的最大面积.html
岛屿数量
岛屿深搜
-
两种写法:可以把终止条件写在前面 也可以写在循环内;
- 区别:把判断条件写在main函数或写在dfs函数中
-
采用递归
深搜方法1:停止条件在主函数中
def dfs(graph,visited,x,y,count): directions = [[0,-1],[0,1],[1,0],[-1,0]] for dir_ in directions: nextx = x+dir_[0] nexty = y+dir_[1] if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph): continue if graph[nextx][nexty]==1 and visited[nextx][nexty]==0: visited[nextx][nexty] = 1 ##执行访问 dfs(graph,visited,nextx,nexty,count) def main(): ## 初始化 n,m = map(int,input().split()) graph = [[0]*(m) for _ in range(n)] visited = [[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]) #分别统计 count = 0 for i in range(n): for j in range(m): ##停止条件 if graph[i][j]==1 and visited[i][j]==0: count+=1 dfs(graph,visited,i,j,count) print(count) if __name__ == '__main__': main()
深搜方法2:停止条件在递归函数中
def dfs(graph,visited,x,y): if visited[x][y] or graph[x][y]==0: return visited[x][y] = True dirs = [[0,-1],[0,1],[1,0],[-1,0]] for i in range(4): nextx = x+dirs[i][0] nexty = y+dirs[i][1] if (nextx)<0 or nextx>=len(graph) or nexty<0 or nexty>=len(graph[0]): continue dfs(graph,visited,nextx,nexty) 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 = [[False]*(m) for _ in range(n)] ##递归计数 count = 0 for i in range(n): for j in range(m): if not visited[i][j] and graph[i][j]==1: count+=1 dfs(graph,visited,i,j) print(count) if __name__ == '__main__': main()
岛屿广搜
-
不需要递归
-
加入队列即为访问过了
广度搜索代码
def dfs(graph,visited,x,y,count): directions = [[0,-1],[0,1],[1,0],[-1,0]] queue = [[x,y]] while queue: curr = queue.pop() x = curr[0] y = curr[1] visited[x][y] = 1 for dir_ in directions: nextx = x+dir_[0] nexty = y+dir_[1] if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph): continue if graph[nextx][nexty]==1 and visited[nextx][nexty]==0: visited[nextx][nexty] = 1 dfs(graph,visited,nextx,nexty,count) def main(): ## 初始化 n,m = map(int,input().split()) graph = [[0]*(m) for _ in range(n)] visited = [[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]) #分别统计 count = 0 for i in range(n): for j in range(m): if graph[i][j]==1 and visited[i][j]==0: count+=1 dfs(graph,visited,i,j,count) print(count)
岛屿最大面积
-
和岛屿广搜一样的
深度优先搜索1
def dfs(graph,visited,x,y): if graph[x][y]==0 or visited[x][y]==1: return 0 count = 1 visited[x][y] = 1 directions = [[0,1],[0,-1],[1,0],[-1,0]] for dir_ in directions: nextx = x+dir_[0] nexty = y+dir_[1] if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph): continue if graph[nextx][nexty]==1 and visited[nextx][nexty]==0: count += dfs(graph,visited,nextx,nexty) return count def main(): ## 初始化 n,m = map(int,input().split()) graph = [[0]*(m) for _ in range(n)] visited = [[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]) #分别统计 res = 0 for i in range(n): for j in range(m): ##停止条件 if graph[i][j]==1 and visited[i][j]==0: # visited[i][j] = 1 # count = 0 count = dfs(graph,visited,i,j) res = max(res,count) print(res) if __name__ == '__main__': main()
深度优先搜索2
def dfs(graph,visited,x,y,count): directions = [[0,1],[0,-1],[1,0],[-1,0]] for dir_ in directions: nextx = x+dir_[0] nexty = y+dir_[1] if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph): continue if graph[nextx][nexty]==1 and visited[nextx][nexty]==0: visited[nextx][nexty] = 1 ##执行访 count+=1 count = dfs(graph,visited,nextx,nexty,count) return count def main(): ## 初始化 n,m = map(int,input().split()) graph = [[0]*(m) for _ in range(n)] visited = [[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]) #分别统计 res = 0 for i in range(n): for j in range(m): ##停止条件 if graph[i][j]==1 and visited[i][j]==0: visited[i][j] = 1 count = 1 count = dfs(graph,visited,i,j,count) res = max(res,count) print(res) if __name__ == '__main__': main()
广度优先搜索
def dfs(graph,visited,x,y): queue = [[x,y]] directions = [[0,1],[0,-1],[1,0],[-1,0]] count = 1 visited[x][y] = 1 while queue: curr = queue.pop() x = curr[0] y = curr[1] for dir_ in directions: nextx = x+dir_[0] nexty = y+dir_[1] if nexty<0 or nexty>=len(graph[0]) or nextx<0 or nextx>=len(graph): continue if graph[nextx][nexty]==1 and visited[nextx][nexty]==0: visited[nextx][nexty]=1 count+=1 queue.append([nextx,nexty]) return count def main(): ## 初始化 n,m = map(int,input().split()) graph = [[0]*(m) for _ in range(n)] visited = [[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]) #分别统计 res = 0 for i in range(n): for j in range(m): ##停止条件 if graph[i][j]==1 and visited[i][j]==0: count = dfs(graph,visited,i,j) res = max(res,count) print(res) if __name__ == '__main__': main()