← 返回题目列表

Codeforces · 1015/E1

E1. 星星图画(简易版)

中文机器翻译题面 查看原题

星形是以下类型的图形:图形中心的星号字符“*”和具有相同正长度的四条射线(向左、向右、顶部、底部)。恒星的大小是其射线的长度。恒星的大小必须是正数(即不允许长度为 $$$0$$$ 的光线)。

假设空单元格用“.”表示,那么下面的数字就是星号:

最左边的图形是大小为 $$$1$$$ 的星星,中间的图形是大小为 $$$2$$$ 的星星,最右边的图形是大小为 $$$3$$$ 的星星。

给您一个大小为 $$$n \times m$$$ 的矩形网格,仅由星号“*”和句点(点)“.”组成。行的编号从 $$$1$$$ 到 $$$n$$$,列的编号从 $$$1$$$ 到 $$$m$$$。你的任务是使用任意数量的星星绘制这个网格,或者发现这是不可能的。星星可以交叉、重叠,甚至重合。输出中的星星数量不能超过 $$$n \cdot m$$$。每颗星星都应该完全位于网格内。您可以使用相同或任意大小的星星。

在这个问题中,您不需要最小化星星的数量。只要找到任何方法来绘制给定的网格,最多包含 $$$n \cdot m$$$ 星星。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n, m \le 100$$$) — 给定网格的大小。

接下来的 $$$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$$$ 是星号的大小。每颗星星都应该完全位于网格内。

示例

输入 #1

6 8
....*...
...**...
..*****.
...**...
....*...
........

输出 #1

3
3 4 1
3 5 2
3 5 1

输入 #2

5 5
.*...
****.
.****
..**.
.....

输出 #2

3
2 2 1
3 3 1
3 4 1

输入 #3

5 5
.*...
***..
.*...
.*...
.....

输出 #3

-1

输入#4

3 3
*.*
.*.
*.*

输出#4

-1

注意

在第一个示例中,输出

也是正确的。