2D-префиксные суммы и минимизация потерь внутренности — задача «Смайло и Minecraft» РАЗБОР

Источник задачи: региональный этап Олимпиады им. М.В. Келдыша, 2025, задача C.

Что дано

Прямоугольное поле размера $m \times n$ клеток. Каждая клетка содержит один из трёх символов: . (пустая клетка), # (камень) или g (золотой слиток). Параметр $k$ задаёт радиус взрыва.

Взрыв можно выполнить в любой пустой клетке $(x, y)$ внутри поля. При взрыве действует квадрат со стороной $2k+1$, центрированный на $(x, y)$. Механика взрыва:

• Все клетки квадрата становятся пустыми (камни и слитки исчезают).
• Слитки строго внутри квадрата (в подквадрате $(2k-1) \times (2k-1)$, не на границе) — теряются.
• Слитки на периметре квадрата (внешний слой шириной в одну клетку) — собираются.

Квадрат может выходить за пределы поля — клетки за границей поля ни на что не влияют. Разрешено выполнять произвольное число взрывов. Нужно найти максимум слитков, которые можно собрать.

Ограничения

• $1 \leq m, n, k \leq 500$
• Хотя бы одна клетка поля гарантированно пуста (иначе первый взрыв невозможен).

Формат ввода

Первая строка — три числа $m$, $n$, $k$ через пробел. Далее — $m$ строк по $n$ символов каждая, описывающих поле построчно.

Формат вывода

Одно целое число — максимальное количество собранных слитков.

Примеры

Пример 1. Поле $2 \times 3$, $k = 1$:

2 3 1
#.#
g.g

Ожидаемый ответ: 2.

Пример 3. Поле $3 \times 4$, $k = 2$:

3 4 2
.gg.
g...
g##.

Ожидаемый ответ: 4 (все слитки поля).

Пример 1 руками

m=2, n=3, k=1
#.#
g.g

Квадрат взрыва со стороной $2k+1 = 3$. Центр — любая из пустых клеток $(0, 1)$ или $(1, 1)$. Квадрат $3 \times 3$ с центром $(0, 1)$ займёт строки $-1..1$ и столбцы $0..2$.

«Строго внутри» — это строки $0..0$ и столбцы $1..1$, то есть одна клетка $(0, 1)$ — сам центр, который пустой. Потерь нет.

«На периметре» — 8 клеток по границе квадрата. В пределах поля: $(0, 0), (0, 2), (1, 0), (1, 1), (1, 2)$. Из них золото на $(1, 0)$ и $(1, 2)$ — собираем 2 слитка.

Ответ: 2. ✓

Пример 3 руками

m=3, n=4, k=2
.gg.
g...
g##.

Всего золото: $(0,1), (0,2), (1,0), (2,0)$ — 4 слитка.

Квадрат взрыва $5 \times 5$ ($2k+1 = 5$). «Строго внутри» — квадрат $3 \times 3$ с тем же центром.

Попробуем центр $(2, 3)$ (нижний-правый, пустой). Внутренность — строки $1..3$ и столбцы $2..4$. В пределах поля: строки $1..2$, столбцы $2..3$. Клетки: $(1,2)=., (1,3)=., (2,2)=\#, (2,3)=.$ — золота внутри нет.

Значит при этом первом взрыве мы теряем 0, собираем то, что на периметре в пределах поля — проверим: периметр квадрата это строки $0, 4$ и столбцы $1, 5$. В поле попадает строка 0 (вся $[0, 4]$ → $[1, 3]$ из-за колонок) и столбец $1$ (клетки $(1,1), (2,1)$). Золото: $(0,1)=g, (0,2)=g, (0,3)=.$, $(1,1)=., (2,1)=\#$ — собрали 2 слитка.

Остаются $(1, 0), (2, 0)$. Нужен второй взрыв. После первого взрыва квадрат из строк $[0, 4] \cap [0, 2] = [0, 2]$ и столбцов $[1, 5] \cap [1, 3] = [1, 3]$ уже пустой. Делаем второй взрыв в $(2, 2)$? Но $(2, 2)=\#$, занят. Возьмём $(2, 3)$ — пустая. Квадрат с центром там же, сторона 5, но ключ в том, что мы можем расширить: взрывать на «новом» периметре (квадрат со стороной 7 с тем же центром $(2, 3)$)? Нет — нельзя, сам взрыв всегда фиксированного размера $2k+1$.

Правильно: делаем следующий взрыв так, чтобы новый квадрат захватил ранее непокрытые клетки. Центр нового взрыва смещаем на $1$ клетку — например, $(2, 2)$. Но $(2,2)=\#$, занята. А клетки строки 1 и 2, в столбце 0 — $(1, 0)$ с золотом, $(2, 0)$ с золотом. Хочется центр в $(1, 1)$ (пустая), квадрат строк $-1..3$, столбцов $-1..3$. В поле — всё поле целиком (строки $0..2$, столбцы $0..3$). Всё это становится пустым, и золото $(1, 0)$ и $(2, 0)$ — на периметре квадрата со стороной 5 с центром $(1, 1)$? Периметр — строки $-1$ и $3$, столбцы $-1$ и $3$. Нет, они в столбце 0 и строках 1, 2 — это строго внутри квадрата.

Значит прямой второй взрыв терять будет. Похоже, нужно выбрать другой центр первого взрыва.

Важное наблюдение (оно и есть идея): после первого взрыва можно «перешагивать» взрывами, у которых предыдущий квадрат взрыва становится частью центра — и через несколько шагов дойти до любой оставшейся клетки. Но это работает, только если при каждом следующем взрыве центр находится в уже опустошённой области (пустая клетка), и новый квадрат не содержит потерянного золота во внутренности.

Ключ: если первый взрыв уже потерял какое-то золото, остальное потом собирается целиком — потому что следующие взрывы можно располагать так, чтобы золото всегда оказывалось на периметре.

Об этом ниже.

---

Идея решения

Ключевое наблюдение: «потери только на первом взрыве»

Рассмотрим первый взрыв. Всё золото строго внутри его квадрата ($2k+1$ со стороной) теряется — это фиксированная плата за «начало работы». Но всё остальное золото на поле мы потом соберём гарантированно: достаточно расположить следующие взрывы так, чтобы их центры оказывались на периметре уже расширяемой пустой зоны, а новое золото попадало только на периметры новых квадратов (откуда оно собирается, а не теряется).

Значит задача сводится к минимизации золота внутренности первого квадрата: перебрать все допустимые центры первого взрыва (пустые клетки поля) и выбрать тот, при котором потеря минимальна. Сумма на произвольном квадрате считается за $O(1)$ через 2D-префиксные суммы по позициям золота — значит общая сложность $O(m \cdot n)$.

Пусть первый взрыв в $(x, y)$. Внутри квадрата со стороной $2k+1$ — всё золото строго во внутреннем квадрате $(2k-1) \times (2k-1)$ пропало. Золото на периметре — собрано.

Теперь нужно дойти до остальных клеток. Алгоритм: берём границу следующего квадрата (стороны $2k+3$) с тем же центром — клетки этой границы пока не опустошены (они за пределами первого взрыва). Можно делать новые взрывы, центрируя их на этой границе. Но центр взрыва должен быть в пустой клетке — для этого границы идут изнутри наружу: на границе квадрата $2k+3$ есть клетки, которые на периметре первого взрыва (т.е. были на границе $2k+1$) — они уже пустые. Ставим взрыв центром туда; новый квадрат захватывает ранее непокрытую полосу, и всё золото на её периметре — собираем.

Повторяя, расширяем покрытие квадратами $2k+1$, $2k+3$, $2k+5$, …

Важно: при втором и дальнейших взрывах никакое золото не теряется, потому что:

• Всё, что окажется «внутри» нового квадрата, — это уже ранее опустошённая область (там золота нет).
• Новое золото встречается только на новой границе (которая становится периметром нового взрыва) — значит собирается.

Это геометрически несложно проверить, но требует аккуратной индукции.

Вывод. Пусть $G$ — суммарное количество золота на поле. Минимизируем $L(x, y)$ — количество золота строго внутри квадрата первого взрыва с центром $(x, y)$. Ответ:

$$\text{answer} = G - \min_{(x, y) \in \text{пустые клетки}} L(x, y)$$

Что такое «строго внутри»?

Квадрат со стороной $2k+1$ с центром $(x, y)$ покрывает строки $[x-k, x+k]$ и столбцы $[y-k, y+k]$.

Периметр — первая и последняя строка, первый и последний столбец: $x-k$, $x+k$, $y-k$, $y+k$.

«Строго внутри» — подквадрат строк $[x-k+1, x+k-1]$ и столбцов $[y-k+1, y+k-1]$, то есть размером $(2k-1) \times (2k-1)$. При $k = 1$ это одна клетка $(x, y)$ — сам центр, который пустой по условию, так что $L(x, y) = 0$. Тогда ответ $= G$ всегда, если есть хоть одна пустая клетка.

Как быстро считать $L(x, y)$?

Префиксные суммы по золоту:

$$P[i][j] = \text{количество золота в прямоугольнике } [0..i-1] \times [0..j-1]$$

Тогда сумма в прямоугольнике $[r_1..r_2] \times [c_1..c_2]$ (включительно):

$$S = P[r_2+1][c_2+1] - P[r_1][c_2+1] - P[r_2+1][c_1] + P[r_1][c_1]$$

С учётом клиппинга границ поля $[0, m-1] \times [0, n-1]$. $O(1)$ на запрос, $O(m \cdot n)$ на построение.

Перебираем все $O(m \cdot n)$ пустых клеток — всего $O(m \cdot n)$.

---

Решение: псевдокод

читать m, n, k, сетку
P = 2D-префиксная сумма по g-клеткам
G = P[m][n]                             # всё золото

best_lost = G                           # хуже не бывает
нашли_пустую = false

для каждой (r, c) в сетке:
    если grid[r][c] != '.': continue
    нашли_пустую = true
    r1 = max(0, r - k + 1), r2 = min(m - 1, r + k - 1)
    c1 = max(0, c - k + 1), c2 = min(n - 1, c + k - 1)
    если r1 > r2 или c1 > c2:
        lost = 0
    иначе:
        lost = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
    best_lost = min(best_lost, lost)

если не нашли_пустую:
    вывести 0
иначе:
    вывести G - best_lost

---

Код решения

---

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

Пример 1

2 3 1
#.#
g.g

$G = 2$ (золото на $(1, 0)$ и $(1, 2)$).

$k = 1$, внутренность — 1 клетка. Пустые: $(0, 1)$ и $(1, 1)$. В обеих случаях внутренность — сама эта клетка, золота нет. $L = 0$ для обеих.

Ответ: $2 - 0 = 2$ ✓

Пример 2

2 3 2
#.#
g.g

$G = 2$. $k = 2$, внутренность $3 \times 3$.

• $(0, 1)$: внутренность строки $-1..1$, столбцы $0..2$. Клиппинг: строки $0..1$, столбцы $0..2$. Золото внутри: $(1,0)=g, (1,2)=g$ → $L = 2$.
• $(1, 1)$: внутренность строки $0..2$, столбцы $0..2$. Клиппинг: строки $0..1$, столбцы $0..2$. Золото: то же 2. $L = 2$.

$\min L = 2$. Ответ: $2 - 2 = 0$ ✓

Пример 3

3 4 2
.gg.
g...
g##.

$G = 4$ (золото на $(0,1), (0,2), (1,0), (2,0)$).

$k = 2$, внутренность $3 \times 3$.

Пустые клетки (не # и не g): $(0,0), (0,3), (1,1), (1,2), (1,3), (2,3)$.

Для каждой считаем $L$ на $3 \times 3$:

• $(0, 0)$: строки $-1..1$ → $0..1$, столбцы $-1..1$ → $0..1$. Золото: $(0,1)=g, (1,0)=g$. $L = 2$.
• $(0, 3)$: строки $-1..1$ → $0..1$, столбцы $2..4$ → $2..3$. Золото: $(0,2)=g$. $L = 1$.
• $(1, 1)$: строки $0..2$, столбцы $0..2$. Золото: $(0,1), (0,2), (1,0), (2,0)$ → $L = 4$.
• $(1, 2)$: строки $0..2$, столбцы $1..3$. Золото: $(0,1), (0,2)$ → $L = 2$.
• $(1, 3)$: строки $0..2$, столбцы $2..4$ → $2..3$. Золото: $(0,2)$ → $L = 1$.
• $(2, 3)$: строки $1..3$ → $1..2$, столбцы $2..4$ → $2..3$. Золото: нет (в этом прямоугольнике). $L = 0$.

$\min L = 0$ (клетка $(2, 3)$). Ответ: $4 - 0 = 4$ ✓

---

Крайние случаи

1. Нет золота

$G = 0$. Ответ: 0, независимо от центра.

2. $k = 1$

Внутренность $(2k-1) \times (2k-1) = 1 \times 1$ — одна клетка (сам центр). Центр пустой по условию → $L = 0$ всегда. Ответ: $G$ (всё золото собирается).

3. Квадрат выходит за пределы поля

Клиппинг r1..r2, c1..c2 по границам $[0, m-1], [0, n-1]$. Если пусто (r1 > r2) — $L = 0$.

Это полезно: при взрыве в углу большая часть квадрата — за полем, потерь меньше. Алгоритм учитывает это автоматически.

4. Единственная пустая клетка

Перебор даст ровно один $L$ — он же и ответ.

5. Поле целиком из камней # (кроме одной пустой клетки — гарантируется)

$G = 0$ → ответ $0$.

6. Максимальные $m = n = 500$

Поле $2.5 \cdot 10^5$ клеток, префсумма $O(mn)$ памяти и времени. Перебор — $O(mn)$. Никаких проблем ни по времени, ни по памяти.

---

Типичные ошибки

1. Путаница «внутри» vs «на периметре» vs «весь квадрат». Внимательно: внутренность — это квадрат $(2k-1) \times (2k-1)$, не $(2k+1) \times (2k+1)$.

2. Размер внутренности при $k = 1$. Одна клетка, не пусто. Не путать с $0 \times 0$.

3. Неучёт клиппинга. При взрыве у границы поля не все клетки внутренности существуют. Без клиппинга получишь выход за массив или неправильный счёт.

4. Перебирать не только пустые. Центр обязан быть пустым. Если перебираешь все клетки без фильтра — получаешь неверные $L$ для # и g-клеток (да и брать центром золотой слиток, который исчезнет, — это теряет сам слиток).

5. Забыть про случай found_empty == false. В условии гарантируется хотя бы одна пустая клетка, но хорошо иметь этот защитный путь.

6. Префсумма off-by-one. Классическая ошибка — путать индексы $[r][c]$ и $[r+1][c+1]$. Формула:

$$P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i-1][j-1]$$

---

Сложность

• Время: $O(m \cdot n)$ (построение префсуммы + перебор пустых клеток с $O(1)$ запросами).
• Память: $O(m \cdot n)$ (префсумма).

---

Что ещё полезно потренировать

Задачи на 2D-префиксные суммы + жадный или конструктивный выбор «лучшей стартовой точки»:

• Codeforces 835B «The number on the board» — жадность по цифрам с сортировкой.
• Codeforces 1301B «Disturbed Letters» / 1175A «From Hero to Zero» — перебор с $O(1)$ проверкой.
• Codeforces 1114D «Flood Fill» — DP после интуитивной редукции.
• acmp.ru задача 501 «Магический квадрат» — префсумма 2D + перебор.

Общий мотив: заметить, что ответ — это «что-то от единственного выбора», и свести перебор к $O(mn)$ или $O(n \log n)$ с помощью префсуммы.

---

Итого

• Идея: ответ = всё золото минус минимальная потеря на внутренности квадрата первого взрыва.
• Почему: после первого взрыва оставшееся золото собирается целиком — расширяя покрытие концентрическими квадратами стороны $2k+1, 2k+3, \ldots$
• Инструмент: 2D-префсумма для $O(1)$ запроса суммы в прямоугольнике, перебор $O(m \cdot n)$ пустых клеток.
• Сложность: $O(m \cdot n)$.
• Ловушки: внутренность — $(2k-1) \times (2k-1)$, не $(2k+1) \times (2k+1)$; клиппинг границ поля; перебирать только пустые клетки.