Статья Автор: Дубинин Дмитрий

5

from collections import deque

# Чтение данных
n = int(input())
grid = []
for _ in range(n):
    row = input().strip()
    grid.append(row)

# Массив посещённых клеток
visited = [[False] * n for _ in range(n)]
rooms_count = 0

# Направления: вверх, вниз, влево, вправо
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    for j in range(n):
        # Если нашли пустую клетку, которую ещё не посещали
        if grid[i][j] == '.' and not visited[i][j]:
            rooms_count += 1
            # BFS для поиска всей пещеры
            queue = deque()
            queue.append((i, j))
            visited[i][j] = True
            
            while queue:
                x, y = queue.popleft()
                
                # Проверяем всех соседей
                for d in range(4):
                    nx, ny = x + dx[d], y + dy[d]
                    
                    # Проверяем, что не вышли за границы
                    if 0 <= nx < n and 0 <= ny < n:
                        if grid[nx][ny] == '.' and not visited[nx][ny]:
                            visited[nx][ny] = True
                            queue.append((nx, ny))

print(rooms_count)

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать