题目描述

一扇规模为 $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{请不要输出任何多余的字符（包括但不限于空格和换行符），否则会被判错。}}$

3 5 3
.....
.*.*.
.....

1
+-+..
|*|*.
+-+..

7 6 4
......
.*.*.*
......
.*.*..
..*...
..*...
*....*

2
......
.*.*.*
+--+..
|*.|..
|.*|..
+--+..
*....*

9 9 6
***......
......*.*
.*....*..
..*...*..
..*.*....
..*....*.
.....*...
.*...***.
.........

6
***......
......*.*
.*....*..
..*+----+
..*|*...|
..*|...*|
...|.*..|
.*.|.***|
...+----+

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，$3 \le K \le R,S \le 100$。

【提示与说明】

欢迎大家通过私信或发帖对自行编写的 Special Judge 进行 hack。

题目译自 COCI 2015-2016 #7 Task 2 Prozor。

本题分值按 COCI 原题设置，满分 $80$。