代码随想录算法训练营 Day 44
Published:
Q1. KamaCoder 99
深度优先搜索 - 一条路走到黑，直到无法找到下一个有效点
两种解法：
- 先找到新的坐标点，再判断是否有效
- 先判断当前坐标，再找到新的坐标点
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(x, y):
for dx, dy in directions:
new_x = x + dx
new_y = y + dy
if new_x < 0 or new_y < 0 or new_x >= len(islands) or new_y >= len(islands[0]):
continue
if islands[new_x][new_y] == 1:
islands[new_x][new_y] = 2
dfs(new_x, new_y)
def dfs1(x, y):
if islands[x][y] != 1:
return
islands[x][y] = 2
for dx, dy in directions:
nx = x + dx
ny = y + dy
if nx < 0 or nx >= len(islands) or ny < 0 or ny >= len(islands[0]):
continue
dfs1(nx, ny)
if __name__ == '__main__':
n, m = map(int, input().split())
islands = []
for _ in range(n):
island = list(map(int, input().split()))
islands.append(island)
res = 0
# 解法1
# for i in range(n):
# for j in range(m):
# if islands[i][j] == 1:
# res += 1
# islands[i][j] = 2
# dfs(i, j)
# 解法2
for i in range(n):
for j in range(m):
if islands[i][j] == 1:
res += 1
dfs1(i, j)
# print(islands)
print(res)
广度优先搜索 - 先遍历完当前层所有可能性，再走向下一层
只要加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过
from collections import deque
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def bfs(x, y):
queue = deque([])
queue.append((x, y))
while queue:
curr_x, curr_y = queue.popleft()
for dx, dy in directions:
new_x, new_y = curr_x + dx, curr_y + dy
if new_x < 0 or new_x >= len(islands) or new_y < 0 or new_y >= len(islands[0]):
continue
if islands[new_x][new_y] == 1:
islands[new_x][new_y] = 2
queue.append((new_x, new_y))
if __name__ == '__main__':
n, m = map(int, input().split())
islands = []
for _ in range(n):
island = list(map(int, input().split()))
islands.append(island)
res = 0
for i in range(n):
for j in range(m):
if islands[i][j] == 1:
res += 1
islands[i][j] = 2
bfs(i, j)
print(res)
Q2. KamaCoder 100
和Q1类似，只是现在需要统计每个岛屿的面积，并从中找到最大值
深度优先遍历
directions = [[0, 1], [-1, 0], [0, -1], [1, 0]]
def dfs(x, y, area):
for dx, dy in directions:
nx = x + dx
ny = y + dy
if nx < 0 or nx >= len(grid) or ny < 0 or ny >= len(grid[0]):
continue
if grid[nx][ny] == 1:
grid[nx][ny] = 2
area = dfs(nx, ny, area + 1)
return area
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = 2
count = dfs(i, j, 1)
res = max(res, count)
print(res)
广度优先搜索
from collections import deque
directions = [[0, 1], [-1, 0], [0, -1], [1, 0]]
def bfs(x, y, area):
queue = deque([])
queue.append((x, y))
while queue:
curr_x, curr_y = queue.popleft()
for dx, dy in directions:
nx, ny = curr_x + dx, curr_y + dy
if nx < 0 or nx >= len(grid) or ny < 0 or ny >= len(grid[0]):
continue
if grid[nx][ny] == 1:
grid[nx][ny] = 2
area += 1
queue.append((nx, ny))
return area
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = 2
count = bfs(i, j, 1)
res = max(res, count)
print(res)