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)$.