codeforces-scrape

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

699B.md (1768B)


      1 Source: https://codeforces.com/problemset/problem/699/B
      2 
      3 B. One Bomb
      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 are given a description of a depot. It is a rectangular checkered field of *n* × *m* size. Each cell in a field can be empty (".") or it can be occupied by a wall ("*").
     22 
     23 You have one bomb. If you lay the bomb at the cell (*x*, *y*), then after triggering it will wipe out all walls in the row *x* and all walls in the column *y*.
     24 
     25 You are to determine if it is possible to wipe out all walls in the depot by placing and triggering exactly one bomb. The bomb can be laid both in an empty cell or in a cell occupied by a wall.
     26 
     27 Input
     28 
     29 The first line contains two positive integers *n* and *m* (1 ≤ *n*, *m* ≤ 1000) — the number of rows and columns in the depot field.
     30 
     31 The next *n* lines contain *m* symbols "." and "*" each — the description of the field. *j*-th symbol in *i*-th of them stands for cell (*i*, *j*). If the symbol is equal to ".", then the corresponding cell is empty, otherwise it equals "*" and the corresponding cell is occupied by a wall.
     32 
     33 Output
     34 
     35 If it is impossible to wipe out all walls by placing and triggering exactly one bomb, then print "NO" in the first line (without quotes).
     36 
     37 Otherwise print "YES" (without quotes) in the first line and two integers in the second line — the coordinates of the cell at which the bomb should be laid. If there are multiple answers, print any of them.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 4  
     45 .*..  
     46 ....  
     47 .*..
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 YES  
     54 1 2
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 3 3  
     61 ..*  
     62 .*.  
     63 *..
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 NO
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 6 5  
     76 ..*..  
     77 ..*..  
     78 *****  
     79 ..*..  
     80 ..*..  
     81 ..*..
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 YES  
     88 3 3
     89 ```