Задача №115275. Дорожка вокруг озера
Леся работает ландшафтным дизайнером. Её задача — проложить вокруг озера в парке дорожку, использовав как можно меньше строительных материалов. Дорожку можно строить только на клетках газона.
Парк представляет собой клетчатый прямоугольник размером \(h \times w\), каждая клетка которого это либо земля, либо газон, либо озеро. Вам дана карта парка, на которой отмечены только клетки газона. Гарантируется, что:
- множество клеток газона 4-связно, иначе говоря, можно добраться от любой клетки до любой другой, переходя от клетки к клетке только через общую сторону;
- у множества клеток газона есть ровно одна внутренняя 4-связная область — озеро;
- можно, начав в какой-то клетке газона, пройти по клеткам газона по циклу и вернуться в ту же клетку, переходя каждый раз в соседнюю клетку по стороне, так что озеро окажется внутри этого цикла. Будем говорить, что множество клеток, для которого выполнено это свойство, 4-окружает озеро.
Требуется проложить дорожку по некоторым клеткам газона так, чтобы дорожка 4-окружала озеро, и клеток в дорожке было как можно меньше.
Предложите план прокладывания оптимальной дорожки.
В первой строке содержатся натуральные числа \(h\) и \(w\) (\(3 \le h, w \le 1000\)) — размеры парка.
Каждая из следующих \(h\) строк содержит \(w\) символов « # » и « . ». Символ « # » означает клетку газона, а символ « . » означает клетку земли или клетку озера.
Выведите \(h\) строк по \(w\) символов — оптимальный план прокладывания дорожки. Символ « # » означает клетку дорожки, а символ « . » означает клетку, не принадлежащую дорожке. Обратите внимание, что дорожку можно прокладывать только по клеткам газона.
Если существует несколько оптимальных планов проложить дорожку, выведите любой из них.
4 6 ###### #.#.## #...#. #####.
#####. #...#. #...#. #####.