codeforces-scrape

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

1881C.md (2000B)


      1 Source: https://codeforces.com/problemset/problem/1881/C
      2 
      3 C. Perfect Square
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 Kristina has a matrix of size $n$ by $n$, filled with lowercase Latin letters. The value of $n$ is even.
     22 
     23 She wants to change some characters so that her matrix becomes a perfect square. A matrix is called a perfect square if it remains unchanged when rotated $90^\circ$ clockwise once.
     24 
     25 Here is an example of rotating a matrix by $90^\circ$:
     26 
     27  ![](https://espresso.codeforces.com/51a3edf10df0f5f6fab20321012c4b2a23aa41ad.png) 
     28 
     29 In one operation, Kristina can choose any cell and replace its value with the next character in the alphabet. If the character is equal to "z", its value does not change.
     30 
     31 Find the minimum number of operations required to make the matrix a perfect square.
     32 
     33 For example, if the $4$ by $4$ matrix looks like this:
     34 
     35 $$\matrix{ a & b & b & a \cr b & c & \textbf{b} & b \cr b & c & c & b\cr a & b & b & a \cr }$$
     36 
     37 then it is enough to apply $1$ operation to the letter b, highlighted in bold.
     38 
     39 Input
     40 
     41 The first line of the input contains a single integer $t$ ($1 \le t \le 10^2$) — the number of test cases.
     42 
     43 Then follows the description of each test case.
     44 
     45 The first line of each test case contains a single even integer $n$ ($2 \le n \le 10^3$) — the number of rows and columns in the matrix.
     46 
     47 Then follows $n$ lines, each containing exactly $n$ lowercase Latin letters.
     48 
     49 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^3$.
     50 
     51 Output
     52 
     53 For each test case, output a single number on a separate line: the minimum number of operations required for Kristina to obtain a perfect square.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 5
     61 
     62 4
     63 
     64 abba
     65 
     66 bcbb
     67 
     68 bccb
     69 
     70 abba
     71 
     72 2
     73 
     74 ab
     75 
     76 ba
     77 
     78 6
     79 
     80 codefo
     81 
     82 rcesco
     83 
     84 deforc
     85 
     86 escode
     87 
     88 forces
     89 
     90 codefo
     91 
     92 4
     93 
     94 baaa
     95 
     96 abba
     97 
     98 baba
     99 
    100 baab
    101 
    102 4
    103 
    104 bbaa
    105 
    106 abba
    107 
    108 aaba
    109 
    110 abba
    111 ```
    112 
    113 Output
    114 
    115 ```
    116 1
    117 2
    118 181
    119 5
    120 9
    121 ```
    122 
    123 Note
    124 
    125 The first test case is explained in the problem statement.