| Codeforces Round 706 (Div. 1) |
|---|
| Закончено |
В Солнечном огороде растет много подсолнухов.
Солнечный огород представляет из себя прямоугольную таблицу из $$$n$$$ строк и $$$m$$$ столбцов, где в каждой ячейке находится грядка. На всех грядках раньше росли подсолнухи. К сожалению, одной ночью молния ударила в несколько (возможно, ноль) ячеек, и некоторые подсолнухи были сожжены. Другими словами, некоторые ячейки таблицы стали пустыми. Что удивительно, никакие две пустые ячейки не имеют общих точек (ни сторон, ни углов).
Сейчас владелица участка хочет убрать еще несколько (возможно, ноль) подсолнухов так, чтобы были выполнены следующие два условия:
- Из любой пустой клетки можно добраться в любую другую пустую клетку. Другими словами, пустые клетки связны.
- Между любыми двумя пустыми клетками существует ровно один простой путь. Другими словами, в пустых клетках нет циклов.
Из одной пустой клетки можно перейти в другую, если и только если они имеют общую сторону.
Ваша задача — предложить владелице, какие подсолнухи нужно убрать, чтобы оба условия были выполнены.
Обратите внимание, что вы не можете сажать подсолнухи. Также обратите внимание, что вам не нужно минимизировать число убранных подсолнухов. Можно показать, что решение всегда существует.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n,m \le 500$$$) — количество строк и количество столбцов.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов. Каждый символ — либо «X», либо «.», что обозначает, соответственно, пустую клетку и клетку с подсолнухом.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.
Для каждого набора входных данных выведите $$$n$$$ строк. Каждая строка должна содержать $$$m$$$ символов, описывающих очередную строку таблицы. Каждый символ должен быть равен либо «X», либо «.», что обозначает, соответственно, пустую клетку и клетку с подсолнухом.
Если существует несколько решений, выведите любое из них. Можно показать, что решение всегда существует.
5 3 3 X.X ... X.X 4 4 .... .X.X .... .X.X 5 5 .X... ....X .X... ..... X.X.X 1 10 ....X.X.X. 2 2 .. ..
XXX ..X XXX XXXX .X.X .X.. .XXX .X... .XXXX .X... .X... XXXXX XXXXXXXXXX .. ..
Будем использовать запись $$$(x,y)$$$ для обозначения клетки в $$$x$$$-й строке и $$$y$$$-м столбце.
На следующих изображениях белые, желтые и синие клетки обозначают клетки с подсолнухами, клетки, куда ударила молния, и убранные в решении подсолнухи, соответственно.
В первом наборе входных данных одно из решений — убрать подсолнухи в клетках $$$(1,2)$$$, $$$(2,3)$$$ и $$$(3 ,2)$$$.
Другое возможное решение — убрать подсолнухи из клеток $$$(1,2)$$$, $$$(2,2)$$$ и $$$(3,2)$$$.
Данное решение — неверное, так как между любыми двумя клетками есть два простых пути, то есть есть цикл. Например, между $$$(1,1)$$$ и $$$(3,3)$$$ есть два таких пути:
- $$$(1,1)\to (1,2)\to (1,3)\to (2,3)\to (3,3)$$$
- $$$(1,1)\to (2,1)\to (3,1)\to (3,2)\to (3,3)$$$
Данное решение неверное, так как между пустыми клетками $$$(1,1)$$$ и $$$(3,3)$$$ нельзя пройти.
