Реши задание на изображении

Краткий ответ

Задачу можно решить за \(O(nm)\), если не искать кластеры целиком, а считать каждую единичную грань отдельно.

Пусть \(B\) — количество синих клеток в одном слое.
Сначала посчитаем \(H\) — число граничных боковых граней внутри одного слоя:

• снаружи по периметру слоя всегда \(2(n+m)\) граней;
• для каждой пары соседних клеток внутри слоя добавляем 1, если они не срастаются.

Пара не срастается, если это не «обе \(R\)» и не «обе \(G\)». То есть \(B\)-\(B\) в одном слое тоже даёт границу.

Тогда ответ:

\[ \text{answer}=k\cdot H+2nm+(k-1)(nm-B) \]

Почему вертикальная часть такая:

• если клетка не синяя, то её копии в соседних слоях не срастаются: на столбик из \(k\) клеток приходится \(k+1\) граничная грань;
• если клетка синяя, все \(k\) копий срастаются в один столбик: остаются только 2 внешние грани сверху и снизу.

После суммирования получается формула выше.

Код на Python 3

import sys


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    m = int(data[1])
    k = int(data[2])

    grid = data[3:3 + n]

    B = ord('B')
    R = ord('R')
    G = ord('G')

    b_count = 0
    h = 2 * (n + m)

    # Горизонтальные соседства внутри одного слоя
    for i in range(n):
        row = grid[i]
        b_count += row.count(b'B')

        for x, y in zip(row, row[1:]):
            # Срастаются только одинаковые R или G.
            if not (x == y and (x == R or x == G)):
                h += 1

    # Вертикальные соседства внутри одного слоя
    for i in range(1, n):
        up = grid[i - 1]
        down = grid[i]

        for x, y in zip(up, down):
            if not (x == y and (x == R or x == G)):
                h += 1

    nm = n * m

    ans = k * h + 2 * nm + (k - 1) * (nm - b_count)
    print(ans)


if __name__ == "__main__":
    solve()

Проверка на примерах с картинки:

• 2 3 2 / RRG / RBG → 45
• 1 1 1 / R → 6
• 1 2 1 / BB → 11

Сложность: \(O(nm)\) по времени и \(O(nm)\) по памяти.