codeforces-scrape

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

828B.md (1938B)


      1 Source: https://codeforces.com/problemset/problem/828/B
      2 
      3 B. Black Square
      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 Polycarp has a checkered sheet of paper of size *n* × *m*. Polycarp painted some of cells with black, the others remained white. Inspired by Malevich's "Black Square", Polycarp wants to paint minimum possible number of white cells with black so that all black cells form a square.
     22 
     23 You are to determine the minimum possible number of cells needed to be painted black so that the black cells form a black square with sides parallel to the painting's sides. All the cells that do not belong to the square should be white. The square's side should have positive length.
     24 
     25 Input
     26 
     27 The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 100) — the sizes of the sheet.
     28 
     29 The next *n* lines contain *m* letters 'B' or 'W' each — the description of initial cells' colors. If a letter is 'B', then the corresponding cell is painted black, otherwise it is painted white.
     30 
     31 Output
     32 
     33 Print the minimum number of cells needed to be painted black so that the black cells form a black square with sides parallel to the painting's sides. All the cells that do not belong to the square should be white. If it is impossible, print -1.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 5 4  
     41 WWWW  
     42 WWWB  
     43 WWWB  
     44 WWBB  
     45 WWWW
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 5
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 1 2  
     58 BB
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 -1
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 3 3  
     71 WWW  
     72 WWW  
     73 WWW
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 1
     80 ```
     81 
     82 Note
     83 
     84 In the first example it is needed to paint 5 cells — (2, 2), (2, 3), (3, 2), (3, 3) and (4, 2). Then there will be a square with side equal to three, and the upper left corner in (2, 2).
     85 
     86 In the second example all the cells are painted black and form a rectangle, so it's impossible to get a square.
     87 
     88 In the third example all cells are colored white, so it's sufficient to color any cell black.