代码随想录算法训练营 Day 45
Published:
Q1. KamaCoder 101
孤岛是指不靠边的陆地，可以先将所有与边界靠近的陆地标记，然后再遍历所有岛屿，找到面积总和
深度优先搜索
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(x, y, c=0):
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
c = dfs(nx, ny, c + 1)
return c
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
for i in range(n):
if grid[i][0] == 1:
grid[i][0] = 2
dfs(i, 0)
if grid[i][m - 1] == 1:
grid[i][m - 1] = 2
dfs(i, m - 1)
for j in range(m):
if grid[0][j] == 1:
grid[0][j] = 2
dfs(0, j)
if grid[n - 1][j] == 1:
grid[n - 1][j] = 2
dfs(n - 1, j)
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = 2
res += dfs(i, j, 1)
print(res)
广度优先搜索
只要加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过
from collections import deque
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def bfs(x, y, area=0):
queue = deque([])
queue.append((x, y))
while queue:
curr_x, curr_y = queue.popleft()
for dx, dy in directions:
nx = curr_x + dx
ny = 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())))
for i in range(n):
if grid[i][0] == 1:
grid[i][0] = 2
bfs(i, 0)
if grid[i][m - 1] == 1:
grid[i][m - 1] = 2
bfs(i, m - 1)
for j in range(m):
if grid[0][j] == 1:
grid[0][j] = 2
bfs(0, j)
if grid[n - 1][j] == 1:
grid[n - 1][j] = 2
bfs(n - 1, j)
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = 2
res += bfs(i, j, 1)
print(res)
Q2. KamaCoder 102
和Q1类似，只是现在需要将所有孤岛变成海，因此将靠近边界的所有陆地设置为2，并且在后面将其重新设置成1
深度优先遍历
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(x, y):
for dx, dy in directions:
nx, ny = x + dx, 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
dfs(nx, ny)
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
for i in range(n):
if grid[i][0] == 1:
grid[i][0] = 2
dfs(i, 0)
if grid[i][m - 1] == 1:
grid[i][m - 1] = 2
dfs(i, m - 1)
for j in range(m):
if grid[0][j] == 1:
grid[0][j] = 2
dfs(0, j)
if grid[n - 1][j] == 1:
grid[n - 1][j] = 2
dfs(n - 1, j)
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = 0
if grid[i][j] == 2:
grid[i][j] = 1
for line in grid:
print(' '.join(map(str, line)))
广度优先搜索
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:
cx, cy = queue.popleft()
for dx, dy in directions:
nx, ny = cx + dx, cy + 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
queue.append((nx, ny))
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
for i in range(n):
if grid[i][0] == 1:
grid[i][0] = 2
bfs(i, 0)
if grid[i][m - 1] == 1:
grid[i][m - 1] = 2
bfs(i, m - 1)
for j in range(m):
if grid[0][j] == 1:
grid[0][j] = 2
bfs(0, j)
if grid[n - 1][j] == 1:
grid[n - 1][j] = 2
bfs(n - 1, j)
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = 0
if grid[i][j] == 2:
grid[i][j] = 1
for line in grid:
print(' '.join(map(str, line)))
Q3. KamaCoder 103
逆向思维：要找到能够同时流向第一边界和第二边界的格子，也就是说从第一边界和第二边界出发都能到达这个格子
深度优先搜索
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(x, y, flag):
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] >= grid[x][y]:
if flag == 1 and (nx, ny) not in visited1:
visited1.add((nx, ny))
dfs(nx, ny, flag)
elif flag == 2 and (nx, ny) not in visited2:
visited2.add((nx, ny))
dfs(nx, ny, flag)
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
visited1 = set()
for i in range(n):
visited1.add((i, 0))
dfs(i, 0, 1)
for j in range(m):
visited1.add((0, j))
dfs(0, j, 1)
visited2 = set()
for i in range(n):
visited2.add((i, m - 1))
dfs(i, m - 1, 2)
for j in range(m):
visited2.add((n - 1, j))
dfs(n - 1, j, 2)
res = visited1 & visited2
for x, y in res:
print(x, y)
广度优先搜索
from collections import deque
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def bfs(x, y, flag):
queue = deque([])
queue.append((x, y))
while queue:
cx, cy = queue.popleft()
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] >= grid[cx][cy]:
if flag == 1 and (nx, ny) not in visited1:
visited1.add((nx, ny))
queue.append((nx, ny))
elif flag == 2 and (nx, ny) not in visited2:
visited2.add((nx, ny))
queue.append((nx, ny))
if __name__ == '__main__':
n, m = map(int, input().split())
grid = []
for _ in range(n):
grid.append(list(map(int, input().split())))
visited1 = set()
for i in range(n):
visited1.add((i, 0))
bfs(i, 0, 1)
for j in range(m):
visited1.add((0, j))
bfs(0, j, 1)
visited2 = set()
for i in range(n):
visited2.add((i, m - 1))
bfs(i, m - 1, 2)
for j in range(m):
visited2.add((n - 1, j))
bfs(n - 1, j, 2)
res = visited1 & visited2
for x, y in res:
print(x, y)
Q4. KamaCoder 104
运行两次搜索，第一次将岛屿进行标记，并且存储每块岛屿的面积；第二次找到海的位置，并且判断将其变为陆地后最大的岛屿面积
注意点：
- 第二次遍历只需要看不同方向的四个格子即可，并且对于同一块岛屿，只能统计一次
- 有整块全是陆地，不存在海的特殊情况
深度优先搜索
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def dfs(x, y, tag, area):
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 1:
grid[nx][ny] = tag
area = dfs(nx, ny, tag, 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())))
area_with_tag = {0:0}
t = 2
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = t
a = dfs(i, j, t, 1)
area_with_tag[t] = a
t += 1
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 0:
max_merged_area = 1
vis = set()
for dx, dy in directions:
surrounding_x, surrounding_y = i + dx, j + dy
if 0 <= surrounding_x < len(grid) and 0 <= surrounding_y < len(grid[0]) and grid[surrounding_x][surrounding_y] not in vis:
max_merged_area += area_with_tag[grid[surrounding_x][surrounding_y]]
vis.add(grid[surrounding_x][surrounding_y])
res = max(res, max_merged_area)
if res == 0:
print(n * m)
else:
print(res)
广度优先搜索
from collections import deque
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
def bfs(x, y, tag, area):
queue = deque([(x, y)])
while queue:
cx, cy = queue.popleft()
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 1:
grid[nx][ny] = tag
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())))
area_with_tag = {0:0}
t = 2
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
grid[i][j] = t
a = bfs(i, j, t, 1)
area_with_tag[t] = a
t += 1
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 0:
max_merged_area = 1
vis = set()
for dx, dy in directions:
surrounding_x, surrounding_y = i + dx, j + dy
if 0 <= surrounding_x < len(grid) and 0 <= surrounding_y < len(grid[0]) and grid[surrounding_x][surrounding_y] not in vis:
max_merged_area += area_with_tag[grid[surrounding_x][surrounding_y]]
vis.add(grid[surrounding_x][surrounding_y])
res = max(res, max_merged_area)
if res == 0:
print(n * m)
else:
print(res)