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  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.