E2. Stars Drawing (Hard Edition)

Codeforces

IDCF1015E2

Time3000ms

Memory256MB

Difficulty—

binary searchdpgreedy

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 1000$) — 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 1000$）——给定网格的尺寸。接下来的 $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 1000$）——给定网格的尺寸。接下来的 $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 $ G \in \{*, .\}^{n \times m} $ be the input grid of size $ n \times m $. A *star* centered at $ (x, y) $ with size $ s \in \mathbb{Z}^+ $ is the set of cells: $$ \{(x, y)\} \cup \{(x - i, y) \mid 1 \le i \le s\} \cup \{(x + i, y) \mid 1 \le i \le s\} \cup \{(x, y - i) \mid 1 \le i \le s\} \cup \{(x, y + i) \mid 1 \le i \le s\} $$ A star is *valid* if all its cells lie within the grid boundaries: $ 1 \le x \pm s \le n $ and $ 1 \le y \pm s \le m $. **Constraints** 1. $ 3 \le n, m \le 1000 $ 2. Each cell of $ G $ is either $ * $ or $ . $ 3. Stars may overlap; total number of stars $ k \le n \cdot m $ 4. Each star must have size $ s_j \ge 1 $ and be completely contained in the grid. **Objective** Find a set $ \mathcal{S} = \{(x_j, y_j, s_j) \mid j = 1, \dots, k\} $ of valid stars such that: $$ \bigcup_{j=1}^{k} \text{star}(x_j, y_j, s_j) = \{ (i, j) \in [n] \times [m] \mid G[i][j] = * \} $$ and $ \text{star}(x_j, y_j, s_j) \cap \{ (i, j) \mid G[i][j] = . \} = \emptyset $ for all $ j $. If no such set $ \mathcal{S} $ 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": "E2. Stars Drawing (Hard 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": "CF1015E2"
  },
  "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 $ G \\in \\{*, .\\}^{n \\times m} $ be the input grid of size $ n \\times m $.  \nA *star* centered at $ (x, y) $ with size $ s \\in \\mathbb{Z}^+ $ is the set of cells:  \n$$\n\\{(x, y)\\} ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments