2021.11.08/dfs/棋局评估
https://www.acwing.com/problem/content/description/3263/
debug无情机器

//debug一小时哭了
#include<bits/stdc++.h>
using namespace std;

int g[4][4];
int tt, oo;

int check(){
    for(int i = 0; i < 3; i++){
        if(g[i][0] == g[i][1] && g[i][1] == g[i][2] && g[i][2]) return g[i][2];
        if(g[0][i] == g[1][i] && g[1][i] == g[2][i] && g[2][i]) return g[2][i];
    }
    if(g[0][0] == g[1][1] && g[1][1] == g[2][2] && g[2][2]) return g[2][2];
    if(g[0][2] == g[1][1] && g[1][1] == g[2][0] && g[1][1]) return g[1][1];
    return 0;
}

int dfs(int u){
    if(check()){
        if(check() == 1) return u + 1;
        else return - u - 1;
    }
    if(u == 0) return 0;
    int f12 = 20, f21 = -20, f0 = 0, f11 = 0, f22 = 0, tmp;

    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++){
            if(!g[i][j]){
                g[i][j] = !(u%2) + 1, tmp = dfs(u - 1), g[i][j] = 0;

                if(tmp == 0) f0 = 1;
                else if(tmp < 0) f22 = min(f22, tmp), f21 = max(f21, tmp);
                else if(tmp > 0) f11 = max(f11, tmp), f12 = min(f12, tmp); 
            }
        }

    if(u % 2 && f11) return f11;
    else if(!(u % 2) && f22 < 0) return f22;
    if(f0) return 0;
    if(u % 2) return f21;
    return f12;
}

int main(){
    cin >> tt;
    while(tt--){
        oo = 0;
        for(int i = 0; i < 9; i++) cin >> g[i/3][i%3], oo += !g[i/3][i%3];
        cout << dfs(oo) << endl;
    }
}