codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1015E1.md (2712B)


      1 Source: https://codeforces.com/problemset/problem/1015/E1
      2 
      3 E1. Stars Drawing (Easy Edition)
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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).
     22 
     23 Let's consider empty cells are denoted by '.', then the following figures are stars:
     24 
     25  ![](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$. 
     26 
     27 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.
     28 
     29 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.
     30 
     31 Input
     32 
     33 The first line of the input contains two integers $n$ and $m$ ($3 \le n, m \le 100$) — the sizes of the given grid.
     34 
     35 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.
     36 
     37 Output
     38 
     39 If it is impossible to draw the given grid using stars only, print "-1".
     40 
     41 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.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 6 8  
     49 ....*...  
     50 ...**...  
     51 ..*****.  
     52 ...**...  
     53 ....*...  
     54 ........
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 3  
     61 3 4 1  
     62 3 5 2  
     63 3 5 1
     64 ```
     65 
     66 Input
     67 
     68 ```
     69 5 5  
     70 .*...  
     71 ****.  
     72 .****  
     73 ..**.  
     74 .....
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 3  
     81 2 2 1  
     82 3 3 1  
     83 3 4 1
     84 ```
     85 
     86 Input
     87 
     88 ```
     89 5 5  
     90 .*...  
     91 ***..  
     92 .*...  
     93 .*...  
     94 .....
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 -1
    101 ```
    102 
    103 Input
    104 
    105 ```
    106 3 3  
    107 *.*  
    108 .*.  
    109 *.*
    110 ```
    111 
    112 Output
    113 
    114 ```
    115 -1
    116 ```
    117 
    118 Note
    119 
    120 In the first example the output
    121 
    122 ```
    123 2  
    124 3 4 1  
    125 3 5 2
    126 ```
    127 
    128 is also correct.