文章目录
- 99.岛屿数量
- DFS
- BFS
- 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:
continue
if (visited[x][y]==False) and (islands[x][y] == 1):
visited[x][y] = True
dfs([x,y], islands, visited)
if __name__ == '__main__':
nums = 0
NM = 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 += 1
visited[i][j] = True
dfs([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:
continue
if islands[x][y] == 1 and visited[x][y] == False:
st.append([x, y])
visited[x][y] = True
100.岛屿的最大面积
和上一题基本一致,在BFS/DFS的时候记录一下面积,最后选最大的面积输出。
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def bfs(cur, islands, visited):
st = [cur]
area = 1
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:
continue
if islands[x][y] == 1 and visited[x][y] == False:
area += 1
st.append([x, y])
visited[x][y] = True
return area
if __name__ == '__main__':
area = 0
NM = 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] = True
area = max(bfs([i,j], islands, visited), area)
print(area)