【代码随想录算法训练营第五十七天|卡码网99. 岛屿数量、100.岛屿的最大面积】

99.岛屿数量

DFS

创建一个同样大小的列表记录每一个区域是否被访问过，对于每一位置遍历，如果遇到了1并且没有访问过那就岛屿数量+1，然后把该区域的访问设置为True，然后用dfs去把这个位置接壤的为1的区域全都设置为已经访问过，这样之后遍历遇到就不会再计算入内。

direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]def dfs(cur, islands, visited):N = len(islands)M = len(islands[0])for d in direction:x = cur[0] + d[0]y = cur[1] + d[1]if x < 0 or x >= N or y < 0 or y >= M:continueif (visited[x][y]==False) and (islands[x][y] == 1):visited[x][y] = Truedfs([x,y], islands, visited)if __name__ == '__main__':nums = 0NM = input().split()N, M = int(NM[0]), int(NM[1])islands = [[0] * M for _ in range(N)]for i in range(N):lands = input().split()for j in range(M):islands[i][j] = int(lands[j])visited = [[False] * M for _ in range(N)]for i in range(N):for j in range(M):if (islands[i][j] == 1) and (visited[i][j]==False):nums += 1visited[i][j] = Truedfs([i,j], islands, visited)print(nums)

BFS

只需要把DFS改成DFS，在遍历到岛屿区域后对该位置进行BFS，在这区域的上下左右，如果一个区域没有被访问过且为1那么就设定该位置为访问过并且加入都队列中，直到队列为空。

def bfs(cur, islands, visited):st = [cur]while st:cur = st.pop()for d in direction:x = d[0] + cur[0]y = d[1] + cur[1]if x < 0 or x >= N or y < 0 or y >= M:continueif islands[x][y] == 1 and visited[x][y] == False:st.append([x, y])visited[x][y] = True

100.岛屿的最大面积

direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]def bfs(cur, islands, visited):st = [cur]area = 1while st:cur = st.pop()for d in direction:x = d[0] + cur[0]y = d[1] + cur[1]if x < 0 or x >= N or y < 0 or y >= M:continueif islands[x][y] == 1 and visited[x][y] == False:area += 1st.append([x, y])visited[x][y] = Truereturn areaif __name__ == '__main__':area = 0NM = input().split()N, M = int(NM[0]), int(NM[1])islands = [[0] * M for _ in range(N)]for i in range(N):lands = input().split()for j in range(M):islands[i][j] = int(lands[j])visited = [[False] * M for _ in range(N)]for i in range(N):for j in range(M):if (islands[i][j] == 1) and (visited[i][j]==False):visited[i][j] = Truearea = max(bfs([i,j], islands, visited), area)print(area)