← 返回题目列表

Codeforces · 370/D

D. 显示器损坏

中文机器翻译题面 查看原题

Innocentius 有一个问题 — 他的电脑显示器坏了。现在有些像素“死了”,即它们始终是黑色的。因此,Innocentius 无法玩通常的电脑游戏。他最近正在和他的弟弟波利卡波斯玩以下游戏。

Innocentius 正在触摸打字一个程序,该程序会在黑色屏幕上绘制一个白色方形单像素宽框。由于显示器损坏,一些本应是白色的像素仍然是黑色的。波利卡普斯应该看看程序在屏幕上显示的内容,并猜测英诺森提乌斯绘制的框架的位置和大小。波利卡普斯不喜欢这个游戏,但英诺森提乌斯说服哥哥玩,因为“这个游戏有利于想象力和注意力”。

帮助Polycarpus,使他在游戏过程中的部分自动化。编写代码来找到这样的可能的方框:

- 框架的宽度为 1 像素,
- 框架不超出屏幕边界,
- 显示器的所有白色像素都位于框架上,
- 在满足前面三个条件的所有帧中,所需的帧必须具有最小的尺寸。

形式上,正方形框架由实心正方形的像素表示,这些像素位于正方形的边界上,即不完全被正方形的其他像素包围。例如,如果帧的大小为 d = 3,则它由 8 个像素组成,如果其大小为 d = 2,则它包含 4 个像素,如果 d = 1,则该帧缩小为单个像素。

输入

第一行包含显示器的分辨率,作为一对整数 n, m (1 ≤ n, m ≤ 2000)。接下来的 n 行每行恰好包含 m 个字符——游戏时显示器像素的状态。特点 ”。” (句号,ASCII码46)对应黑色像素,字符“w”(小写英文字母w)对应白色像素。保证显示器至少有一个像素是白色的。

输出

打印监视器屏幕。用字符“+”(“加号”字符)表示所查找的帧。游戏过程中变白的像素不得更改。将它们打印为“w”。如果有多种可能的方法来定位最小尺寸的框架,请打印其中任何一种。

如果所需的帧不存在,则打印包含数字 -1 的单行。

示例

输入 #1

4 8
..w..w..
........
........
..w..w..

输出 #1

..w++w..
..+..+..
..+..+..
..w++w..

输入 #2

5 6
......
.w....
......
..w...
......

输出 #2

......
+w+...
+.+...
++w...
......

输入 #3

2 4
....
.w..

输出 #3

....
.w..

输入#4

2 6
w..w.w
...w..

输出#4

-1

注意

在第一个样本中,所需的最佳帧大小等于 4。在第二个样本中,最佳帧的大小等于 3。在第三个样本中,最佳帧的大小为 1。在第四个样本中,所需的帧不存在。