| Codeforces Round 1031 (Div. 2) |
|---|
| Закончено |
Мальчик Смайло играет в Майнкрафт! Чтобы подготовиться к битве с драконом, ему нужно много золотых яблок, а для этого требуется много золота. Поэтому Смайло отправляется в шахту.
Шахта представляет собой прямоугольное клетчатое поле размера $$$n \times m$$$, каждая клетка которого может быть либо золотой рудой, либо камнем, либо пустой клеткой. Смайло может взорвать динамит в любой пустой клетке. При взрыве в пустой клетке с координатами $$$(x, y)$$$ все клетки, находящиеся внутри квадрата со стороной $$$2k + 1$$$ и центром в клетке $$$(x, y)$$$, становятся пустыми. Если золотая руда находилась строго внутри этого квадрата (не на границе), то она исчезает. Если же золотая руда находилась на границе этого квадрата, то Смайло получает это золото.
Взрывать динамит можно только внутри шахты, однако квадрат взрыва может выходить за пределы шахты.
Определите, какое максимальное количество золота сможет собрать Смайло.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n, m, k \leq 500$$$) — количество строк, столбцов и параметр взрыва $$$k$$$, соответственно.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов, каждый из которых равен '.', '#' или 'g', где '.' — пустая клетка, '#' — камень, 'g' — золото. Гарантируется, что хотя бы одна из клеток является пустой.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$2.5 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество золота, которое можно получить.
32 3 1#.#g.g2 3 2#.#g.g3 4 2.gg.g..#g##.
2 0 4
В первом наборе входных данных Смайло может как угодно взорвать динамит в любой свободной клетке и получить $$$2$$$ золота:
Во втором наборе входных данных, как бы Смайло ни действовал, он не сможет получить золото:
В третьем наборе входных данных можно взорвать динамит в правом нижнем углу, тем самым добыв $$$2$$$ золота, а потом сделать взрыв на одну клетку левее, тем самым добыв оставшиеся $$$2$$$ золота:
