codeforces-scrape

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

1703E.md (1731B)


      1 Source: https://codeforces.com/problemset/problem/1703/E
      2 
      3 E. Mirror Grid
      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 You are given a square grid with $n$ rows and $n$ columns. Each cell contains either $0$ or $1$.
     22 
     23 In an operation, you can select a cell of the grid and flip it (from $0 \to 1$ or $1 \to 0$). Find the minimum number of operations you need to obtain a square that remains the same when rotated $0^{\circ}$, $90^{\circ}$, $180^{\circ}$ and $270^{\circ}$.
     24 
     25 The picture below shows an example of all rotations of a grid.
     26 
     27  ![](https://espresso.codeforces.com/857ef282f520fd4f8bbc9dfac1bfa967975365c2.png)
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$) — the size of the grid.
     34 
     35 Then $n$ lines follow, each with $n$ characters $a_{i,j}$ ($0 \leq a_{i,j} \leq 1$) — the number written in each cell.
     36 
     37 Output
     38 
     39 For each test case output a single integer  — the minimum number of operations needed to make the square look the same rotated $0^{\circ}$, $90^{\circ}$, $180^{\circ}$ and $270^{\circ}$.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5
     47 
     48 3
     49 
     50 010
     51 
     52 110
     53 
     54 010
     55 
     56 1
     57 
     58 0
     59 
     60 5
     61 
     62 11100
     63 
     64 11011
     65 
     66 01011
     67 
     68 10011
     69 
     70 11000
     71 
     72 5
     73 
     74 01000
     75 
     76 10101
     77 
     78 01010
     79 
     80 00010
     81 
     82 01001
     83 
     84 5
     85 
     86 11001
     87 
     88 00000
     89 
     90 11111
     91 
     92 10110
     93 
     94 01111
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 1
    101 0
    102 9
    103 7
    104 6
    105 ```
    106 
    107 Note
    108 
    109 In the first test case, we can perform one operations to make the grid $\begin{matrix}0 & 1 & 0\\ 1 & 1 & \color{red}{1}\\ 0 & 1 & 0\end{matrix}$. Now, all rotations of the square are the same.
    110 
    111 In the second test case, all rotations of the square are already the same, so we don't need any flips.