P8033 [COCI 2015/2016 #7] Prozor

On a window of size $R \times S$, there are some flies. You have a fly swatter that can eliminate all flies inside a $K \times K$ rectangular area (excluding the boundary). Choose a placement of the fly swatter so that the number of eliminated flies is maximized. Output the maximum number of flies eliminated and one corresponding placement. If there are multiple valid placements, output any one of them.

The first line contains three integers $R, S, K$. The next $R$ lines each contain $S$ characters: $\texttt{*}$ (a fly) or $\texttt{.}$ (an empty cell). The testdata guarantees that at least one fly can be eliminated.

The first line outputs the maximum number of flies that can be eliminated. If your program only outputs this value correctly, you can get $50\%$ of the score. The next $R$ lines each contain $S$ characters. Based on the input character matrix, modify the four corners of the chosen $K \times K$ rectangle to $\texttt{+}$, the horizontal edges to $\texttt{-}$, and the vertical edges to $\texttt{|}$. The chosen rectangle must lie completely inside the whole matrix. **Note: If you only want to get the $\mathbf{50\%}$ partial score, output only one integer, which is the maximum number of flies eliminated. In this case,** $\red{\mathbf{do\ not\ output\ any\ extra\ characters\ (including\ but\ not\ limited\ to\ spaces\ and\ newline\ characters),\ otherwise\ you\ will\ be\ judged\ wrong.}}$

**Constraints** - For $100\%$ of the testdata, $3 \le K \le R, S \le 100$. **Hints and Notes** Everyone is welcome to hack the self-written [Special Judge](https://www.luogu.com.cn/paste/luaa2ic5) via private messages or posts. **This problem is translated from [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 2 Prozor_.** **The scoring of this problem follows the original COCI problem: full score is $80$.** Translated by ChatGPT 5