Untitled

#include <iostream>

using namespace std;

const int MAX_N = 12;
const int MAX_CORE = 12;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int N;
int board[MAX_N][MAX_N];
int maxConnected, minLength;
int coreCount;
pair<int, int> cores[MAX_CORE];

void input() {
    cin >> N;
    coreCount = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] == 1 && i > 0 && i < N-1 && j > 0 && j < N-1) {
                cores[coreCount++] = {i, j};
            }
        }
    }
}

bool canConnect(int x, int y, int dir) {
    x += dx[dir];
    y += dy[dir];
    while (x >= 0 && x < N && y >= 0 && y < N) {
        if (board[x][y] != 0) return false;
        x += dx[dir];
        y += dy[dir];
    }
    return true;
}

int connectCore(int x, int y, int dir, int value) {
    int length = 0;
    x += dx[dir];
    y += dy[dir];
    while (x >= 0 && x < N && y >= 0 && y < N) {
        board[x][y] = value;
        length++;
        x += dx[dir];
        y += dy[dir];
    }
    return length;
}

void dfs(int idx, int connected, int length) {
    if (idx == coreCount) {
        if (connected > maxConnected || (connected == maxConnected && length < minLength)) {
            maxConnected = connected;
            minLength = length;
        }
        return;
    }

    int x = cores[idx].first;
    int y = cores[idx].second;

    for (int dir = 0; dir < 4; dir++) {
        if (canConnect(x, y, dir)) {
            int wireLength = connectCore(x, y, dir, 2);
            dfs(idx + 1, connected + 1, length + wireLength);
            connectCore(x, y, dir, 0);
        }
    }

    dfs(idx + 1, connected, length);
}

void solve() {
    maxConnected = 0;
    minLength = 1e9;
    dfs(0, 0, 0);
    cout << minLength << endl;
}

int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        input();
        cout << "#" << tc << " ";
        solve();
    }
    return 0;
}