codeforces-scrape

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

1059B.md (2381B)


      1 Source: https://codeforces.com/problemset/problem/1059/B
      2 
      3 B. Forgery
      4 
      5 time limit per test
      6 
      7 2 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 Student Andrey has been skipping physical education lessons for the whole term, and now he must somehow get a passing grade on this subject. Obviously, it is impossible to do this by legal means, but Andrey doesn't give up. Having obtained an empty certificate from a local hospital, he is going to use his knowledge of local doctor's handwriting to make a counterfeit certificate of illness. However, after writing most of the certificate, Andrey suddenly discovered that doctor's signature is impossible to forge. Or is it?
     22 
     23 For simplicity, the signature is represented as an $n\times m$ grid, where every cell is either filled with ink or empty. Andrey's pen can fill a $3\times3$ square without its central cell if it is completely contained inside the grid, as shown below.
     24 
     25 ```
     26 xxx  
     27 x.x  
     28 xxx
     29 ```
     30 
     31 Determine whether is it possible to forge the signature on an empty $n\times m$ grid.
     32 
     33 Input
     34 
     35 The first line of input contains two integers $n$ and $m$ ($3 \le n, m \le 1000$).
     36 
     37 Then $n$ lines follow, each contains $m$ characters. Each of the characters is either '.', representing an empty cell, or '#', representing an ink filled cell.
     38 
     39 Output
     40 
     41 If Andrey can forge the signature, output "YES". Otherwise output "NO".
     42 
     43 You can print each letter in any case (upper or lower).
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 3 3  
     51 ###  
     52 #.#  
     53 ###
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 YES
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 3 3  
     66 ###  
     67 ###  
     68 ###
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 NO
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 4 3  
     81 ###  
     82 ###  
     83 ###  
     84 ###
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 YES
     91 ```
     92 
     93 Input
     94 
     95 ```
     96 5 7  
     97 .......  
     98 .#####.  
     99 .#.#.#.  
    100 .#####.  
    101 .......
    102 ```
    103 
    104 Output
    105 
    106 ```
    107 YES
    108 ```
    109 
    110 Note
    111 
    112 In the first sample Andrey can paint the border of the square with the center in $(2, 2)$.
    113 
    114 In the second sample the signature is impossible to forge.
    115 
    116 In the third sample Andrey can paint the borders of the squares with the centers in $(2, 2)$ and $(3, 2)$:
    117 
    118 1. we have a clear paper:
    119 
    120    ```
    121    ...  
    122    ...  
    123    ...  
    124    ...
    125    ```
    126 2. use the pen with center at $(2, 2)$.
    127 
    128    ```
    129    ###  
    130    #.#  
    131    ###  
    132    ...
    133    ```
    134 3. use the pen with center at $(3, 2)$.
    135 
    136    ```
    137    ###  
    138    ###  
    139    ###  
    140    ###
    141    ```
    142 
    143 In the fourth sample Andrey can paint the borders of the squares with the centers in $(3, 3)$ and $(3, 5)$.