[COCI2015-2016#7] Prozor
题目描述
一扇规模为 $R \times S$ 的窗户上有若干只苍蝇。现有一把苍蝇拍,它可以消灭 $K \times K$ 矩形区域内(不含边界)的所有苍蝇。
请选择一种苍蝇拍的放置位置,使得被消灭的苍蝇数量最多。输出消灭的苍蝇的最大值和该方案。如果有多种符合的方案,请输出任意一种。
输入输出格式
输入格式
第一行,三个整数 $R,S,K$。
接下来的 $R$ 行,每行 $S$ 个字符 $\texttt *$(表示苍蝇)或 $\texttt .$(表示空白区域)。数据保证至少能消灭一只苍蝇。
输出格式
第一行,输出能消灭苍蝇数量的最大值。当程序只答对该值时,可以获得 $50\%$ 的分数。
接下来的 $R$ 行,每行 $S$ 个字符。在输入的字符矩阵的基础上,将所选定的 $K \times K$ 矩形的四个角改为 $\texttt +$、横向边改为 $\texttt -$、纵向边改为 $\texttt |$ 即可。选定的矩形区域必须完全在整个矩阵内部。
**注:如果只想获得 $\mathbf{50\%}$ 的部分分,请只输出一个整数,即消灭苍蝇数量的最大值。此时,** $\red {\mathbf{请不要输出任何多余的字符(包括但不限于空格和换行符),否则会被判错。}}$
输入输出样例
输入样例 #1
3 5 3
.....
.*.*.
.....
输出样例 #1
1
+-+..
|*|*.
+-+..
输入样例 #2
7 6 4
......
.*.*.*
......
.*.*..
..*...
..*...
*....*
输出样例 #2
2
......
.*.*.*
+--+..
|*.|..
|.*|..
+--+..
*....*
输入样例 #3
9 9 6
***......
......*.*
.*....*..
..*...*..
..*.*....
..*....*.
.....*...
.*...***.
.........
输出样例 #3
6
***......
......*.*
.*....*..
..*+----+
..*|*...|
..*|...*|
...|.*..|
.*.|.***|
...+----+
说明
**【数据规模与约定】**
- 对于 $100\%$ 的数据,$3 \le K \le R,S \le 100$。
**【提示与说明】**
欢迎大家通过私信或发帖对自行编写的 [Special Judge](https://www.luogu.com.cn/paste/luaa2ic5) 进行 hack。
**题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 2 Prozor_。**
**本题分值按 COCI 原题设置,满分 $80$。**