Выпуклая оболочка
(Время: 1 сек. Память: 16 Мб Сложность: 27%)
Рассмотрим бесконечный лист клетчатой бумаги. Закрасим некоторое множество клеток в черный цвет. Теперь мы хотим закрасить минимальное количество клеток, так, чтобы множество черных клеток стало выпуклым.
Напомним, что геометрическая фигура Φ называется выпуклой, если для любых точек A из Φ и В из Φ с вещественными координатами отрезок [AB] принадлежит Φ.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два числа N и M
(1 ≤ N, M ≤ 100) — размеры куска бумаги, куда попали все черные клетки. В каждой из следующих N строк содержится М символов «*» или «.». Символ «*» обозначает черную клетку, а «.» белую.
Выходные данные
В выходной файл OUTPUT.TXT выведите выпуклое множество, содержащее минимальное количество дополнительно покрашенных черных клеток, в ровно N строках по M символов «*» или «.» в каждой.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 4
..*.
.**.
| .**.
.**.
|
| 2 | 4 3
.*.
.*.
.*.
.*.
| .*.
.*.
.*.
.*.
|
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
