Задача 45: Удаление клеток
Условие задачи:
Из прямоугольного листа клетчатой бумаги (\(M\) строк, \(N\) столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Входные данные:
В первой строке находятся числа \(M\) и \(N\), в следующих \(M\) строках - по \(N\) символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. \(1 <= M, N <= 100\).
Выходные данные:
Вывести одно число.
Решение:
import sys
sys.setrecursionlimit(10 ** 9)
m, n = map(int, input().split())
u = [["." for _ in range(n + 2)]] + [["."] + [i for i in input()] + ['.'] for _ in range(m)] + [["." for _ in range(n + 2)]]
used = [[False for i in range(n + 2)] for _ in range(m + 2)]
d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
izm = False
def dfs(i, j):
global used, izm
if u[i][j] == '#':
izm = True
used[i][j] = True
else:
return 0
cnt = 1
for g in d:
if u[i + g[0]][j + g[1]] == '#':
if not used[i + g[0]][j + g[1]]:
cnt += dfs(i + g[0], j + g[1])
return cnt
vsv = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if not used[i][j]:
dfs(i, j)
if izm:
vsv += 1
izm = False
print(vsv)
У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик
Пожалуйста, подождите загрузки решения