[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$。**