E1. Stars Drawing (Easy Edition)

Codeforces

IDCF1015E1

Time3000ms

Memory256MB

Difficulty—

brute forcedpgreedy

English · Original

Chinese · Translation

Formal · Original

A _star_ is a figure of the following type: an asterisk character '_*_' in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a _star_ is the length of its rays. The size of a star must be a positive number (i.e. rays of length $0$ are not allowed). Let's consider empty cells are denoted by '_._', then the following figures are _stars_: <center>![image](https://espresso.codeforces.com/8c02b8076a2983adac7612a1a545c6baca48ed49.png) The leftmost figure is a _star_ of size $1$, the middle figure is a _star_ of size $2$ and the rightmost figure is a _star_ of size $3$.</center>You are given a rectangular grid of size $n \times m$ consisting only of asterisks '_*_' and periods (dots) '_._'. Rows are numbered from $1$ to $n$, columns are numbered from $1$ to $m$. Your task is to draw this grid using _any_ number of _stars_ or find out that it is impossible. _Stars_ can intersect, overlap or even coincide with each other. The number of _stars_ in the output can't exceed $n \cdot m$. Each star should be completely inside the grid. You can use stars of same and arbitrary sizes. _In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most $n \cdot m$ stars._ ## Input The first line of the input contains two integers $n$ and $m$ ($3 \le n, m \le 100$) — the sizes of the given grid. The next $n$ lines contains $m$ characters each, the $i$\-th line describes the $i$\-th row of the grid. It is guaranteed that grid consists of characters '_*_' and '_._' only. ## Output If it is impossible to draw the given grid using _stars_ only, print "_\-1_". Otherwise in the first line print one integer $k$ ($0 \le k \le n \cdot m$) — the number of _stars_ needed to draw the given grid. The next $k$ lines should contain three integers each — $x_j$, $y_j$ and $s_j$, where $x_j$ is the row index of the central _star_ character, $y_j$ is the column index of the central _star_ character and $s_j$ is the size of the _star_. Each _star_ should be completely inside the grid. [samples] ## Note In the first example the output 2 3 4 1 3 5 2 is also correct.

一个 _星形_ 是由以下类型的图形构成的：中心位置是一个星号字符 '_*_'，以及四个方向（左、右、上、下）的射线，每条射线长度相同且为正数。星形的大小定义为其射线的长度。星形的大小必须是正数（即长度为 $0$ 的射线是不允许的）。假设空格用 '_._' 表示，则以下图形是 _星形_：给你一个大小为 $n \times m$ 的矩形网格，仅由星号 '_*_' 和点（句点）'_._' 组成。行从 $1$ 到 $n$ 编号，列从 $1$ 到 $m$ 编号。你的任务是使用 _任意数量的_ _星形_ 来绘制这个网格，或者判断这是不可能的。_星形_ 可以相互交叉、重叠甚至完全重合。输出中 _星形_ 的数量不能超过 $n \cdot m$。每个星形必须完全位于网格内部。你可以使用相同或任意大小的星形。 _在本题中，你不需要最小化星形的数量，只需找到一种使用至多 $n \cdot m$ 个星形绘制给定网格的方法即可。_ 输入的第一行包含两个整数 $n$ 和 $m$（$3 \leq n, m \leq 100$）——给定网格的尺寸。接下来的 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行描述网格的第 $i$ 行。保证网格仅由字符 '_*_' 和 '_._' 组成。如果无法仅用 _星形_ 绘制给定网格，请输出 "_-1_"。否则，在第一行输出一个整数 $k$（$0 \leq k \leq n \cdot m$）——绘制给定网格所需的 _星形_ 数量。接下来的 $k$ 行，每行包含三个整数：$x_j$、$y_j$ 和 $s_j$，其中 $x_j$ 是星形中心字符的行索引，$y_j$ 是星形中心字符的列索引，$s_j$ 是星形的大小。每个星形必须完全位于网格内部。在第一个示例中，输出也是正确的。 ## Input 输入的第一行包含两个整数 $n$ 和 $m$（$3 \leq n, m \leq 100$）——给定网格的尺寸。接下来的 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行描述网格的第 $i$ 行。保证网格仅由字符 '_*_' 和 '_._' 组成。 ## Output 如果无法仅用 _星形_ 绘制给定网格，请输出 "_-1_"。否则，在第一行输出一个整数 $k$（$0 \leq k \leq n \cdot m$）——绘制给定网格所需的 _星形_ 数量。接下来的 $k$ 行，每行包含三个整数：$x_j$、$y_j$ 和 $s_j$，其中 $x_j$ 是星形中心字符的行索引，$y_j$ 是星形中心字符的列索引，$s_j$ 是星形的大小。每个星形必须完全位于网格内部。 [samples] ## Note 在第一个示例中，输出 2 3 4 1 3 5 2 也是正确的。

**Definitions** Let $ n, m \in \mathbb{Z} $ be the dimensions of the grid, with $ 3 \leq n, m \leq 100 $. Let $ G \in \{*, .\}^{n \times m} $ be the input grid, where $ G[i][j] $ denotes the character at row $ i $, column $ j $ (1-indexed). A *star* centered at $ (x, y) $ with size $ s \in \mathbb{Z}^+ $ is defined as the set of cells: $$ \{(x, y)\} \cup \{(x - d, y) \mid 1 \leq d \leq s\} \cup \{(x + d, y) \mid 1 \leq d \leq s\} \cup \{(x, y - d) \mid 1 \leq d \leq s\} \cup \{(x, y + d) \mid 1 \leq d \leq s\} $$ A star is *valid* if all its cells lie within the grid bounds: $ 1 \leq x \leq n $, $ 1 \leq y \leq m $, and $ s \geq 1 $, with $ x - s \geq 1 $, $ x + s \leq n $, $ y - s \geq 1 $, $ y + s \leq m $. Let $ \mathcal{S} $ be a multiset of valid stars. **Constraints** 1. $ G[i][j] = * $ if and only if there exists at least one star in $ \mathcal{S} $ covering cell $ (i, j) $. 2. $ G[i][j] = . $ if and only if no star in $ \mathcal{S} $ covers cell $ (i, j) $. 3. $ |\mathcal{S}| \leq n \cdot m $. 4. Each star in $ \mathcal{S} $ has size $ s_j \geq 1 $ and is fully contained in the grid. **Objective** Find a set $ \mathcal{S} = \{(x_j, y_j, s_j)\}_{j=1}^k $ satisfying the above constraints, or determine that no such set exists (output $-1$).

Samples

Input #1

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

Output #1

Input #2

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

Output #2

Input #3

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

Output #3

\-1

Input #4

3 3
*.*
.*.
*.*

Output #4

\-1

API Response (JSON)

{
  "problem": {
    "name": "E1. Stars Drawing (Easy Edition)",
    "description": {
      "content": "A _star_ is a figure of the following type: an asterisk character '_*_' in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a _star_ is",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1015E1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A _star_ is a figure of the following type: an asterisk character '_*_' in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a _star_ is...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一个 _星形_ 是由以下类型的图形构成的：中心位置是一个星号字符 '_*_'，以及四个方向（左、右、上、下）的射线，每条射线长度相同且为正数。星形的大小定义为其射线的长度。星形的大小必须是正数（即长度为 $0$ 的射线是不允许的）。\n\n假设空格用 '_._' 表示，则以下图形是 _星形_：\n\n给你一个大小为 $n \\times m$ 的矩形网格，仅由星号 '_*_' 和点（句点）'_._' 组成。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the dimensions of the grid, with $ 3 \\leq n, m \\leq 100 $.  \nLet $ G \\in \\{*, .\\}^{n \\times m} $ be the input grid, where $ G[i][j] $ denotes the chara...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments