| Hello 2025 |
|---|
| Закончено |
Каждую субботу Александр Б., преподаватель параллели X, вечером пишет Александру Г., преподавателю параллели B, секретное сообщение. Так как Александр Г. в это время проводит лекцию, а сообщение очень важное, то Александру Б. приходится писать это сообщение на интерактивной онлайн-доске.
Интерактивная онлайн-доска представляет собой клетчатое поле, состоящее из $$$n$$$ строк и $$$m$$$ столбцов, где каждая клетка имеет размер $$$1 \times 1$$$. Некоторые клетки этой доски уже расписаны, и в них невозможно написать сообщение; такие клетки обозначены символом «.», остальные клетки называются свободными и обозначаются символом «#».
Введем две характеристики онлайн-доски:
- $$$s$$$ — количество свободных клеток.
- $$$p$$$ — периметр клетчатой фигуры, которая образована объединением свободных клеток.
Пусть $$$A$$$ — множество свободных клеток. Ваша цель состоит в том, чтобы найти множество клеток $$$S \subseteq A$$$, удовлетворяющее следующим свойствам:
- $$$|S| \le \frac{1}{5} \cdot (s+p)$$$.
- Любая клетка из $$$A$$$ либо лежит в $$$S$$$, либо имеет общую сторону с некоторой клеткой из $$$S$$$.
Можно показать, что хотя бы одно множество $$$S$$$, удовлетворяющее этим свойствам, существует; вам требуется отыскать любое подходящее.
В первой строке указано число $$$t$$$ ($$$1 \le t \le 80\,000$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных указаны числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^6$$$) — размеры поля.
В последующих $$$n$$$ строках содержится описание поля.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^6$$$.
Для каждого набора выходных данных по $$$n$$$ строк, состоящих из $$$m$$$ символов, где каждый символ кодирует состояние клетки:
- «#» — клетка содержится в $$$A$$$, но не содержится в $$$S$$$;
- «S» — клетка содержится и в $$$A$$$, и в $$$S$$$;
- «.» — клетка не содержится в $$$A$$$ и не содержится в $$$S$$$.
33 3.#.###.#.2 6############3 7###....#.#.######....
.#. #S# .#. #S##S# #S##S# S#S.... #.#.S#S S#S....
В первом примере $$$s=5$$$ и $$$p=12$$$, таким образом, количество клеток в $$$S$$$ не должно превышать $$$\frac{1}{5} \cdot (5+12) = 3.4$$$, то есть $$$|S| \le 3$$$. Заметим, что предъявленное множество $$$S$$$ состоит из $$$1$$$ клетки и, очевидно, удовлетворяет всем ограничениям.
Во втором примере $$$s=12$$$ и $$$p=16$$$, таким образом, количество клеток в $$$S$$$ не должно превышать $$$\frac{1}{5} \cdot (12+16)= 5.6$$$, то есть $$$|S| \le 5$$$. Заметим, что предъявленное множество $$$S$$$ состоит из $$$4$$$ клеток и, очевидно, удовлетворяет всем ограничениям.
На третьем примере мы объясним, что такое периметр, так как это может быть не очевидно. Любая клетчатая фигура имеет границу, которая представляется в виде объединения отрезков, которые не пересекаются по внутренним точкам. Таким образом, на картинке ниже толстой черной линией обозначена граница фигуры, которая получается путем объединения свободных клеток. Суммарная длина этих отрезков равна $$$p=24$$$.
При этом значение $$$s=11$$$ и верхнее ограничение равно $$$|S| \le 7$$$, предъявленное множество имеет размер $$$6$$$ и, очевидно, удовлетворяет всем ограничениям.
