Broken Monitor

题意翻译

## 描述 小 A 的电脑显示器坏了，有些像素点一直是黑色的。他最近正在和他的弟弟小 B 玩一个游戏：小 A 控制程序在屏幕上绘制一个 1 像素宽的白色方框，由于显示器已经损坏了，一些应该是白色的像素点仍为黑色。小 B 根据屏幕上显示的内容来推测方框的大小和绘制的位置。你要帮助小 B 自动化这个游戏的过程。写一个程序找到满足条件的方框：（1）方框的宽为 1 像素；（2）方框不会超过屏幕的边缘；（3）屏幕显示的白色像素都在方框上；（4）在满足前三个条件的所有方框中，正确的方框是尺寸最小的那个。方框的尺寸由边长表示，方框边缘的像素不重叠。举例来说，边长为 3 的方框包含 8 个像素，边长为 2 的方框包含 4 个像素，边长为 1 的方框包含 1 个像素。 ## 输入格式 第一行包含两个正整数 n , m （1≤n,m≤2000 ），接下来的 n 行，每行包含 m 个c字符，表示游戏过程中显示器像素的状态。字符 . （ASCII 46）对应黑色像素，字符 w（小写英文字母 w）对应白色像素。保证至少有一个像素是白色像素。 ## 输出格式 输出屏幕上的内容。推测出的方框边缘用 + 表示，原来已经是 w 的白色像素保持不变。如果有多个最小尺寸的方框同时存在，输出任意一个。如果这种方框不存在，输出 −1 。 翻译:Xuorange

题目描述

Innocentius has a problem — his computer monitor has broken. Now some of the pixels are "dead", that is, they are always black. As consequence, Innocentius can't play the usual computer games. He is recently playing the following game with his younger brother Polycarpus. Innocentius is touch-typing a program that paints a white square one-pixel wide frame on the black screen. As the monitor is broken, some pixels that should be white remain black. Polycarpus should look at what the program displayed on the screen and guess the position and size of the frame Innocentius has painted. Polycarpus doesn't like the game but Innocentius persuaded brother to play as "the game is good for the imagination and attention". Help Polycarpus, automatize his part in the gaming process. Write the code that finds such possible square frame that: - the frame's width is 1 pixel, - the frame doesn't go beyond the borders of the screen, - all white pixels of the monitor are located on the frame, - of all frames that satisfy the previous three conditions, the required frame must have the smallest size. Formally, a square frame is represented by such pixels of the solid square, that are on the square's border, that is, are not fully surrounded by the other pixels of the square. For example, if the frame's size is $ d=3 $ , then it consists of 8 pixels, if its size is $ d=2 $ , then it contains 4 pixels and if $ d=1 $ , then the frame is reduced to a single pixel.

输入输出格式

输入格式

The first line contains the resolution of the monitor as a pair of integers $ n $ , $ m $ ( $ 1<=n,m<=2000 $ ). The next $ n $ lines contain exactly $ m $ characters each — the state of the monitor pixels at the moment of the game. Character "." (period, ASCII code 46) corresponds to the black pixel, and character "w" (lowercase English letter w) corresponds to the white pixel. It is guaranteed that at least one pixel of the monitor is white.

输出格式

Print the monitor screen. Represent the sought frame by characters "+" (the "plus" character). The pixels that has become white during the game mustn't be changed. Print them as "w". If there are multiple possible ways to position the frame of the minimum size, print any of them. If the required frame doesn't exist, then print a single line containing number -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

说明

In the first sample the required size of the optimal frame equals 4. In the second sample the size of the optimal frame equals 3. In the third sample, the size of the optimal frame is 1. In the fourth sample, the required frame doesn't exist.