codeforces-scrape

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

329A.md (3273B)


      1 Source: https://codeforces.com/problemset/problem/329/A
      2 
      3 A. Purification
      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 You are an adventurer currently journeying inside an evil temple. After defeating a couple of weak zombies, you arrived at a square room consisting of tiles forming an *n* × *n* grid. The rows are numbered 1 through *n* from top to bottom, and the columns are numbered 1 through *n* from left to right. At the far side of the room lies a door locked with evil magical forces. The following inscriptions are written on the door:
     22 
     23  The cleaning of all evil will awaken the door! 
     24 
     25 Being a very senior adventurer, you immediately realize what this means. You notice that every single cell in the grid are initially evil. You should purify all of these cells.
     26 
     27 The only method of tile purification known to you is by casting the "Purification" spell. You cast this spell on a single tile — then, all cells that are located in the same row and all cells that are located in the same column as the selected tile become purified (including the selected tile)! It is allowed to purify a cell more than once.
     28 
     29 You would like to purify all *n* × *n* cells while minimizing the number of times you cast the "Purification" spell. This sounds very easy, but you just noticed that some tiles are particularly more evil than the other tiles. You cannot cast the "Purification" spell on those particularly more evil tiles, not even after they have been purified. They can still be purified if a cell sharing the same row or the same column gets selected by the "Purification" spell.
     30 
     31 Please find some way to purify all the cells with the minimum number of spells cast. Print -1 if there is no such way.
     32 
     33 Input
     34 
     35 The first line will contain a single integer *n* (1 ≤ *n* ≤ 100). Then, *n* lines follows, each contains *n* characters. The *j*-th character in the *i*-th row represents the cell located at row *i* and column *j*. It will be the character 'E' if it is a particularly more evil cell, and '.' otherwise.
     36 
     37 Output
     38 
     39 If there exists no way to purify all the cells, output -1. Otherwise, if your solution casts *x* "Purification" spells (where *x* is the minimum possible number of spells), output *x* lines. Each line should consist of two integers denoting the row and column numbers of the cell on which you should cast the "Purification" spell.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 .E.  
     48 E.E  
     49 .E.
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 1 1  
     56 2 2  
     57 3 3
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 3  
     64 EEE  
     65 E..  
     66 E.E
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 -1
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 5  
     79 EE.EE  
     80 E.EE.  
     81 E...E  
     82 .EE.E  
     83 EE.EE
     84 ```
     85 
     86 Output
     87 
     88 ```
     89 3 3  
     90 1 3  
     91 2 2  
     92 4 4  
     93 5 3
     94 ```
     95 
     96 Note
     97 
     98 The first example is illustrated as follows. Purple tiles are evil tiles that have not yet been purified. Red tile is the tile on which "Purification" is cast. Yellow tiles are the tiles being purified as a result of the current "Purification" spell. Green tiles are tiles that have been purified previously.
     99 
    100  ![](https://espresso.codeforces.com/4ec2ab5188b59377530d96f3bd0454190158eee1.png) 
    101 
    102 In the second example, it is impossible to purify the cell located at row 1 and column 1.
    103 
    104 For the third example:
    105 
    106  ![](https://espresso.codeforces.com/1391da23c40cc6c202bc64b0013f693238e80bf0.png)