1182B.md (1954B)
1 Source: https://codeforces.com/problemset/problem/1182/B 2 3 B. Plus from Picture 4 5 time limit per test 6 7 1 second 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 You have a given picture with size $w \times h$. Determine if the given picture has a single "+" shape or not. A "+" shape is described below: 22 23 * A "+" shape has one center nonempty cell. 24 * There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction. 25 * All other cells are empty. 26 27 Find out if the given picture has single "+" shape. 28 29 Input 30 31 The first line contains two integers $h$ and $w$ ($1 \le h$, $w \le 500$) — the height and width of the picture. 32 33 The $i$-th of the next $h$ lines contains string $s_{i}$ of length $w$ consisting "." and "*" where "." denotes the empty space and "*" denotes the non-empty space. 34 35 Output 36 37 If the given picture satisfies all conditions, print "YES". Otherwise, print "NO". 38 39 You can output each letter in any case (upper or lower). 40 41 Examples 42 43 Input 44 45 ``` 46 5 6 47 ...... 48 ..*... 49 .****. 50 ..*... 51 ..*... 52 ``` 53 54 Output 55 56 ``` 57 YES 58 ``` 59 60 Input 61 62 ``` 63 3 5 64 ..*.. 65 ****. 66 .*... 67 ``` 68 69 Output 70 71 ``` 72 NO 73 ``` 74 75 Input 76 77 ``` 78 7 7 79 ....... 80 ...*... 81 ..****. 82 ...*... 83 ...*... 84 ....... 85 .*..... 86 ``` 87 88 Output 89 90 ``` 91 NO 92 ``` 93 94 Input 95 96 ``` 97 5 6 98 ..**.. 99 ..**.. 100 ****** 101 ..**.. 102 ..**.. 103 ``` 104 105 Output 106 107 ``` 108 NO 109 ``` 110 111 Input 112 113 ``` 114 3 7 115 .*...*. 116 ***.*** 117 .*...*. 118 ``` 119 120 Output 121 122 ``` 123 NO 124 ``` 125 126 Input 127 128 ``` 129 5 10 130 .......... 131 ..*....... 132 .*.******. 133 ..*....... 134 .......... 135 ``` 136 137 Output 138 139 ``` 140 NO 141 ``` 142 143 Note 144 145 In the first example, the given picture contains one "+". 146 147 In the second example, two vertical branches are located in a different column. 148 149 In the third example, there is a dot outside of the shape. 150 151 In the fourth example, the width of the two vertical branches is $2$. 152 153 In the fifth example, there are two shapes. 154 155 In the sixth example, there is an empty space inside of the shape.