백준 9079 동전게임

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
    static int t;
    static int min;
    
    public static void main (String[] args) throws java.lang.Exception
    {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        t = Integer.parseInt(st.nextToken());
        while(t-- > 0) {
            int[][] map = new int[3][3];
            min  = Integer.MAX_VALUE;
            for (int i = 0; i< 3; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j< 3; j++) {
                    String s = st.nextToken();
                    map[i][j] = s.equals("H") ? 1 : 0;
                }
            }
            solve(map, 0, 0);
            if (min == Integer.MAX_VALUE) {
                System.out.println("-1");
            } else {
                System.out.println(min);
            }
        }
    }
    static boolean check(int[][] map) {
        int pivot = map[0][0];
        
        for (int i = 0; i< 3; i++) {
            for (int j = 0; j< 3; j++) {
                if (map[i][j] != pivot) {
                    return false;
                } 
                    
            }
        }
        return true;
    }
    static void solve(int[][] map, int cnt, int idx) {
        
        
        //check
        if (check(map)) {
            min = Math.min(min, cnt);
            return;
        }
        if (idx == 8) {
            return;
        }
        
        solve(map, cnt, idx + 1);
        if (idx < 3) {
            for (int i = 0; i< 3; i++) {
                map[idx][i] = (map[idx][i] == 1 ? 0 : 1);
            }
            solve(map, cnt+1, idx + 1);
            for (int i = 0; i< 3; i++) {
                map[idx][i] = (map[idx][i] == 1 ? 0 : 1);
            }
            
        } else if (idx < 6) {
            for (int i = 0; i< 3; i++) {
                map[i][idx - 3] = (map[i][idx - 3] == 1 ? 0 : 1);
            }
            solve(map, cnt + 1, idx + 1);
            for (int i = 0; i< 3; i++) {
                map[i][idx - 3] = (map[i][idx - 3] == 1 ? 0 : 1);
            }
        } else if (idx == 6) {
            for (int i = 0; i< 3; i++) {
                map[i][i] = (map[i][i] == 1 ? 0 : 1);
            }
            solve(map, cnt +1, idx + 1);
            for (int i = 0; i< 3; i++) {
                map[i][i] = (map[i][i] == 1 ? 0 : 1);
            }
        } else if (idx == 7) {
            for (int i =0; i<3; i++) {
                map[i][2 -i] = (map[i][2 - i] == 1 ? 0 : 1);
                
            }
            solve(map, cnt + 1, idx + 1);
            for (int i =0; i<3; i++) {
                map[i][2 -i] = (map[i][2 - i] == 1 ? 0 : 1);
                
            }
       
        }
        
    }
}