| Author: | Антон Карабанов | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 512 Mb | |
| Output file: | Standard output |
We are already used to advanced algorithms for automatic image processing. With their help, it costs us nothing to remove the background from the photo, cover up the wrinkles and even make a joint collage with any celebrity. But have you ever wondered how such programs work? Is it difficult to write them? You are presented with a simple task: find and remove a single extra character from an ASCII picture.
A picture of size n × m contains an image of an empty rectangle one pixel thick and one extra pixel, denoted by "#" symbols (ASCII code 35). The rectangle is at least three pixels long and three pixels wide, and its sides are parallel to the edges of the image. The background of the picture is filled with "." (ASCII code 46).
The first line of the input contains two integers: n and m. The next n lines contain strings of length m, consisting of the characters "#" and ".".
Output n lines of m characters each — the same image with an extra pixel removed.
3 ≤ n, m ≤ 100
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|
Найдем первую строку, в которой есть не менее трех подряд идущих символа # (очевидно, что в этой строке присутствует верхняя линия прямоугольника). Определим первое и последнее вхождение подстроки ### в этой строке как возможные координаты левой и правой сторон прямоугольника.
Найдем последнюю строку, в которой есть не менее трех подряд идущих символа # (очевидно, что в этой строке присутствует нижняя линия прямоугольника). Определим первое и последнее вхождение подстроки ### в этой строке как возможные координаты левой и правой сторон прямоугольника.
Сравним найденные координаты левой и правой сторон для верхней и нижний линий прямоугольника. Они могут не совпадать в случае, когда лишний символ примыкает к верхней или нижней линии. В этом случае выбираем самую левую из правых или самую правую из левых границ, по которым уже можно однозначно определить границы исходного прямоугольника.