| Codeforces Round 501 (Div. 3) |
|---|
| Закончено |
Звезда — это фигура на клетчатом поле следующего вида: символ звездочка '*' в центре фигуры и четыре луча (влево, вправо, вверх и вниз) одинаковой положительной длины. Размером звезды является длина ее лучей. Размер звезды должен быть строго положительным (то есть лучи длины $$$0$$$ недопустимы).
Пусть пустые клетки обозначены как '.'. Тогда, например, следующие фигуры являются звездами:
Левая фигура — звезда размера $$$1$$$, средняя фигура — звезда размера $$$2$$$ и правая фигура — звезда размера $$$3$$$. Задано прямоугольное поле размера $$$n \times m$$$, состоящее из звездочек '*' и точек '.'. Строки пронумерованы от $$$1$$$ до $$$n$$$, столбцы пронумерованы от $$$1$$$ до $$$m$$$. Ваша задача — нарисовать это поле при помощи любого количества звезд или понять, что это невозможно сделать. Звезды могут пересекаться, вкладываться и даже совпадать друг с другом. Количество звезд в ответе не может превышать $$$n \cdot m$$$. Каждая из звезд должна находиться строго внутри поля. Вы можете использовать звёзды как одинаковых так и различных размеров.
В этой задаче нет необходимости минимизировать количество звезд. Необходимо найти любой способ нарисовать заданное поле при помощи не более, чем $$$n \cdot m$$$ звезд.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n, m \le 1000$$$) — размер заданного поля.
Следующие $$$n$$$ строк содержат $$$m$$$ символов каждая, $$$i$$$-я строка описывает $$$i$$$-ю строку поля. Гарантируется, что поле состоит только из символов '*' и '.'.
Если невозможно нарисовать заданное поле только при помощи некоторого количества звезд , выведите «-1».
Иначе в первой строке выедите $$$k$$$ ($$$0 \le k \le n \cdot m$$$) — количество звезд, необходимое, чтобы нарисовать заданное поле. Следующие $$$k$$$ строк должны содержать по три целых числа каждая — $$$x_j$$$, $$$y_j$$$ и $$$s_j$$$, где $$$x_j$$$ это номер строки центрального символа звезды, $$$y_j$$$ — номер столбца центрального символа звезды и $$$s_j$$$ — размер звезды. Каждая из звезд должна находиться строго внутри поля.
6 8
....*...
...**...
..*****.
...**...
....*...
........
3
3 4 1
3 5 2
3 5 1
5 5
.*...
****.
.****
..**.
.....
3
2 2 1
3 3 1
3 4 1
5 5
.*...
***..
.*...
.*...
.....
-1
3 3
*.*
.*.
*.*
-1
В первом примере вывод
2
3 4 1
3 5 2
тоже является корректным.
