Задача 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)

Задача 45: Удаление клеток

Условие задачи:

Входные данные:

Выходные данные:

Решение:

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик

Пожалуйста, подождите загрузки решения