Выпуклая оболочка (27%)

Ссылка на задачу

Время: 1 сек.
Память: 16 Мб
Сложность: 27%

Определение 1:

Рассмотрим бесконечный лист клетчатой бумаги. Закрасим некоторое множество клеток в черный цвет. Теперь мы хотим закрасить минимальное количество клеток, так, чтобы множество черных клеток стало выпуклым.

Напомним, что геометрическая фигура Φ называется выпуклой, если для любых точек A из Φ и В из Φ с вещественными координатами отрезок [AB] принадлежит Φ.

Формат ввода

В первой строке входного файла input.txt содержатся два числа N и M (1 ≤ N, M ≤ 100) — размеры куска бумаги, куда попали все черные клетки. В каждой из следующих N строк содержится М символов «*» или «.». Символ «*» обозначает черную клетку, а «.» белую.

Формат вывода

В выходной файл output.txt выведите выпуклое множество, содержащее минимальное количество дополнительно покрашенных черных клеток, в ровно N строках по M символов «*» или «.» в каждой./p>

Примеры

Ввод	Вывод
2 4 ..*. .**.	.**. .**.
4 3 .*. .*. .*. .*.	.*. .*. .*. .*.