codeforces-scrape

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

389B.md (1990B)


      1 Source: https://codeforces.com/problemset/problem/389/B
      2 
      3 B. Fox and Cross
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Fox Ciel has a board with *n* rows and *n* columns. So, the board consists of *n* × *n* cells. Each cell contains either a symbol '.', or a symbol '#'.
     22 
     23 A cross on the board is a connected set of exactly five cells of the board that looks like a cross. The picture below shows how it looks.
     24 
     25 ![](https://espresso.codeforces.com/8aebe96074fa8ca8707579b275691fbbd5a285bc.png)
     26 
     27 Ciel wants to draw several (may be zero) crosses on the board. Each cross must cover exactly five cells with symbols '#', and any cell with symbol '#' must belong to some cross. No two crosses can share a cell.
     28 
     29 Please, tell Ciel if she can draw the crosses in the described way.
     30 
     31 Input
     32 
     33 The first line contains an integer *n* (3 ≤ *n* ≤ 100) — the size of the board.
     34 
     35 Each of the next *n* lines describes one row of the board. The *i*-th line describes the *i*-th row of the board and consists of *n* characters. Each character is either a symbol '.', or a symbol '#'.
     36 
     37 Output
     38 
     39 Output a single line with "YES" if Ciel can draw the crosses in the described way. Otherwise output a single line with "NO".
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 5  
     47 .#...  
     48 ####.  
     49 .####  
     50 ...#.  
     51 .....
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 YES
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 4  
     64 ####  
     65 ####  
     66 ####  
     67 ####
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 NO
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 6  
     80 .#....  
     81 ####..  
     82 .####.  
     83 .#.##.  
     84 ######  
     85 .#..#.
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 YES
     92 ```
     93 
     94 Input
     95 
     96 ```
     97 6  
     98 .#..#.  
     99 ######  
    100 .####.  
    101 .####.  
    102 ######  
    103 .#..#.
    104 ```
    105 
    106 Output
    107 
    108 ```
    109 NO
    110 ```
    111 
    112 Input
    113 
    114 ```
    115 3  
    116 ...  
    117 ...  
    118 ...
    119 ```
    120 
    121 Output
    122 
    123 ```
    124 YES
    125 ```
    126 
    127 Note
    128 
    129 In example 1, you can draw two crosses. The picture below shows what they look like.
    130 
    131 ![](https://espresso.codeforces.com/aa9413f448a28b42015ead3c419c032fb3640b8e.png)
    132 
    133 In example 2, the board contains 16 cells with '#', but each cross contains 5. Since 16 is not a multiple of 5, so it's impossible to cover all.