| Когнитивные технологии. Финал 2024 |
|---|
| Finished |
Вам дано клеточное поле $$$n \times m$$$. Некоторые клетки имеют углубления, в которые можно вставлять фигурки; они обозначены символом «.», остальные клетки обозначены символом «#».
Также у вас есть фигурки трех видов, которые вы можете вставлять в любые свободные клетки поля. Они изображены на рисунке ниже:
Ваша задача состоит в том, чтобы заполнить все свободные клетки указанными фигурками или сказать, что это невозможно.
Первая строка ввода содержит одно число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следуют описания наборов.
Первая строка каждого набора содержит пару чисел $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 10^6$$$) — высоту и ширину поля, соответственно.
Затем следуют $$$n$$$ строк, каждая из которых состоит из $$$m$$$ символов «.» или «#».
Сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^6$$$.
Для каждого набора входных данных выведите «No», если ответа не существует.
В ином случае в первой строке выведите «Yes», а затем выведите $$$n$$$ строк, каждая из которых состоит из $$$m$$$ чисел от $$$0$$$ до $$$10^9$$$. Клетки, в которых нет фигурок, должны быть обозначены числом $$$0$$$, а остальные клетки могут содержать произвольные числа, при чем каждая фигурка должна быть обозначена множеством клеток, содержащих одинаковые числа.
36 6#....#.#..#..............#..#.#....#4 4....#..##..#....4 7...#.....###.....#.....###..
Yes 0 1 1 2 2 0 1 0 1 2 0 2 1 1 3 3 2 2 4 4 3 3 5 5 4 0 4 5 0 5 0 4 4 5 5 0 No No
