[Codeforces Round #806 (Div. 4)] E. Mirror Grid

 

---

 

※ 짝수의 경우 왼쪽 상단(2사분면)만 확인해주면 모든 셀을 방문할 수 있음.

    홀수의 경우 중앙이 추가되기 때문에 x좌표나 y좌표 중 하나를 추가로 확인해주어 g셀을 제외한 모든 셀을 탐색하게 해야됨 (i < (n+1)/2 -> 짝수의 경우 5/2 홀수가 되기 때문에 문제없다. 홀수의 경우 6/2 로 열을 한 번 더 탐색해준다.)

 

※ 중앙 셀을 제외한 모든 셀은 다음과 같이 이동한다.

   a좌표 - [0,0] -> [0,3] -> [3,3] -> [3,0]

   b좌표 - [0,1] -> [1,3] -> [3,2] -> [2,0]

 홀수의 경우

  c좌표 - [2,0] -> [0,2] -> [2, 4] -> [4,2]

 (x와 y는 처음의 좌표 [x,y] -> [y,x의 반대] -> [x의 반대, y의 반대] -> [y의 반대, x] 다음의 좌표는 y값이 x로 이동하고 x값의 반대가 y값이 된다.)

 

※ 셀은 0과 1 두 가지 경우가 있다. 4가지 경우의 회전(대칭되는 셀은 4개가 있음) 에서 대칭되는 셀의 합은 셀의 값이 1인 셀의 합이다. (0 0 0 1 이면 합은 1이고 1인 셀은 1개)

   이 경우 합은 1인 셀이 1개 있으니 1개만 바꾸면 되고 4 - 합 은 1인 셀의 갯수를 뺀 3개의 0인 셀이 있으니 3개를 바꾸면 된다. (모든 셀을 0이나 1로 만들라는 소리가 아님) 이 중 적은 값을 택한다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			int N = Integer.parseInt(br.readLine());
 			int[][] arr = new int[N][N];
 			for(int i = 0; i < N; i++) {
 				String str = br.readLine();
 				for(int j = 0; j < N; j++) {
 					arr[i][j] = str.charAt(j) - '0';
 				}
 			}
 			int ans = 0;
 			for(int i = 0; i < (N+1)/2; i++) {
 				for(int j = 0; j < N/2; j++) {
 					int x = N-i-1;
 					int y = N-j-1;
 					int sum = arr[i][j];
 					sum += arr[j][x];
 					sum += arr[x][y];
 					sum += arr[y][i];
 					ans += Math.min(sum, 4-sum);
 				}
 			}
 			sb.append(ans).append('\n');
 		}
 		System.out.println(sb);
 	}
}