| Codeforces Round 920 (Div. 3) |
|---|
| Закончено |
Однажды непутёвый озорной стрелок по имени Шел попал на прямоугольное поле размером $$$n \times m$$$, разбитое на единичные квадратики. В каждой из клеток либо стоит мишень, либо нет.
С собой у Шел оказался только счастливый дробовик, из которого можно выстрелить в одну из четырёх сторон: вправо-вниз, влево-вниз, влево-вверх или вправо-вверх. При выстреле дробовик поражает все мишени в выбранном направлении, Манхэттенское расстояние до которых не больше фиксированной для дробовика константы $$$k$$$. Манхэттенское расстояние между двумя точками $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ равно $$$|x_1 - x_2| + |y_1 - y_2|$$$.
Возможные области поражения для $$$k = 3$$$. Цель Шел — поразить как можно большее количество мишеней. Помогите ему, пожалуйста, найти это значение.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
На ввод в первой строчке даются размеры поля $$$n$$$, $$$m$$$ и константа для мощности дробовика $$$k$$$ ($$$1 \le n, m, k \le 10^5, 1 \le n \cdot m \le 10^5$$$).
В следующих $$$n$$$ строках даётся $$$m$$$ символов — описание очередной строки поля, где символ '.' означает, что клетка пуста, а символ '#' означает наличие мишени. Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора входных данных в отдельной строке выведите одно число, которое равно максимально возможному количеству поражённых мишеней за один выстрел.
43 3 1.#.###.#.2 5 3###.....##4 4 2..#####.#..#####2 1 3##
3 4 5 2
Возможные оптимальные выстрелы для примеров из условия:
