lzysxfcs @ 2024-12-19 12:26:52
from collections import deque
def bfs_ym(n,matrix): #淹没岛屿
visited = [[False]*n for _ in range(n)]
visited[0][0] = True
directions = [(0,1),(0,-1),(1,0),(-1,0)]
queue = deque([(0,0)])
while queue:
x,y = queue.popleft()
for dx,dy in directions:
nx,ny = x+dx,y+dy
if 0 <= nx < n and 0<= ny < n and not visited[nx][ny]:
visited[nx][ny] = True
if matrix[nx][ny] == '#':
for dx,dy in directions:
nnx,nny = nx+dx,ny+dy
if 0 <= nnx < n and 0 <= nny < n and matrix[nnx][nny] == '.':
matrix[nx][ny] = '*'
queue.append((nx,ny))
return matrix
def bfs_num(matrix_ym,n,x,y): #相连的岛屿替换为*,防止重复计算
directions = [(0,1),(0,-1),(1,0),(-1,0)]
queue = deque([(x,y)])
while queue:
x,y = queue.popleft()
for dx,dy in directions:
nx,ny = x+dx,y+dy
if 0 <= nx < n and 0 <= ny < n and matrix_ym[nx][ny] == '#':
matrix[nx][ny] = '*'
queue.append((nx,ny))
n = int(input())
matrix = [list(input()) for _ in range(n)]
matrix_ym = bfs_ym(n,matrix) #淹没之后的岛屿
result = 0 #结果
for i in range(n):
for j in range(n):
if matrix_ym[i][j] == '#':
result +=1
bfs_num(matrix_ym,n,i,j)
print(result)