Задача №115365. Смайло и Minecraft
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Мальчик Смайло играет в Майнкрафт! Чтобы подготовиться к битве с драконом, ему нужно много золотых яблок, а для этого требуется много золота. Поэтому Смайло отправляется в шахту.
Шахта представляет собой прямоугольное клетчатое поле размера \(m \times n\) (\(m\) строк и \(n\) столбцов), каждая клетка которого может быть либо золотым слитком, либо камнем, либо пустой клеткой. Смайло может взорвать динамит в любой пустой клетке поля. При взрыве в пустой клетке с координатами \((x, y)\) все клетки, находящиеся внутри квадрата со стороной \(2k + 1\) и центром в клетке \((x, y)\), становятся пустыми. Если золотой слиток находился строго внутри этого квадрата, то он исчезает. Если золотой слиток находился на периметре этого квадрата, то Смайло получает это золото.
Взрывать динамит можно только внутри шахты, однако квадрат взрыва может выходить за пределы шахты.
Определите, какое максимальное количество слитков золота сможет собрать Смайло, осуществляя для этого любое количество взрывов.
Первая строка содержит три целых числа \(m\) (количество строк), \(n\) (количество столбцов) и \(k\) — параметр взрыва (\(1 \leq m, n, k \leq 500\)).
Каждая из следующих \(m\) строк содержит \(n\) символов, каждый из которых равен '.' , '#' , или 'g' , где '.' — клетка пустая, '#' — камень, 'g' — золото. Гарантируется, что хотя бы одна из клеток является пустой.
Выведите одно число — максимальное количество слитков золота, которое можно получить.
В данной задаче \(25\) тестов, помимо тестов из условия, каждый из них оценивается в \(4\) балла.
Гарантируется, что решения, корректно работающие при \(m, n \leq 5\), наберут не менее \(20\) баллов.
Гарантируется, что решения, корректно работающие при \(m, n \leq 30\), наберут не менее \(40\) баллов.
Гарантируется, что решения, корректно работающие при \(k = 1\), наберут не менее \(20\) баллов.
В первом примере можно взорвать динамит в любой свободной клетке и получить \(2\) слитка золота:
Во втором примере как бы мы ни действовали, мы ничего не заработаем:
В третьем примере можно взорвать динамит в нижнем правом углу, тем самым добыв \(2\) слитка золота, а потом сделать взрыв на одну клетку левее, тем самым добыв оставшиеся \(2\) слитка золота:
2 3 1 #.# g.g
2
2 3 2 #.# g.g
0
3 4 2 .gg. g..# g##.
4