1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

const int INF = 13333;
const int maxn = 407;
int n,t;
void binaryBFS() {}

string graph[maxn];
int distanceMap[maxn][maxn];

int getDistance(int a, int b) {
    return distanceMap[a][b];
}

void setDistance(int a, int b, int d) {
    distanceMap[a][b] = d;
    distanceMap[b][a] = d;
}

void traverseDistances(int t) {
    bool visited[maxn]={false};
    queue<pair<int,int> > q; q.push(make_pair(t, 0));
    while(!q.empty()) {
        pair<int,int> e = q.front(); q.pop();
        if (visited[e.first]) continue;
        setDistance(t, e.first, e.second);
        visited[e.first] = true;
        for (int i = 0; i<n; i++ ) {
            if (i+1 == t) continue;
            if (graph[e.first][i] == '1') {
                q.push(
                    make_pair(
                        i+1,
                        e.second+1
                    )
                );
            }
        }
    }
}

int maxPathAssumingPortalOnPair(int a, int b, int previousScore) {
    int maxPathSoFar = 0;
    for (int i = 1; i<=n; i++) {
        for (int j = i+1; j<=n; j++) {
            int old = distanceMap[i][j]; //getDistance(i, j);
            int fromAtoI = distanceMap[a][i];// getDistance(a, i);
            int fromBtoI = distanceMap[b][i]; // getDistance(b, i);
            int fromAtoJ = distanceMap[a][j]; // getDistance(a, j);
            int fromBtoJ = distanceMap[b][j]; // getDistance(b, j);
            int newPath = min(
                old, min(fromAtoJ, fromBtoJ) + min(fromAtoI, fromBtoI)
            );
            // // cout << "Old distane from " << i << " - " << j << " is " << old << "\n";
            // // cout << "Current distane from " << i << " - " << j << " is " << newPath << "\n";
            maxPathSoFar = max(newPath, maxPathSoFar);
            if (maxPathSoFar > previousScore) return previousScore;
        }
    }
    return maxPathSoFar;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while (t-->0) {
        cin >> n;
        for (int i = 0; i<n; i++) cin >> graph[i+1];
        // calculate base distances from a to b for each pair (default should be infinite)
        for (int i = 1; i<=n; i++) {
            for (int j = i+1; j<=n; j++) {
                setDistance(i, j, INF);
            }
        }
        for (int i = 1; i<=n; i++) {
            traverseDistances(i);
        }

        // now check for each pair how we would reduce the distances
        int v = INF;
        for (int i = 1; i<=n; i++) {
            for (int j = i+1; j<=n; j++) {
                int result = maxPathAssumingPortalOnPair(i, j, v);
                // cout << "Considering portal on: " << i << "-" << j << "\n";
                // cout << "Result: " << result << "\n";
                v = min(v, result);
            }
        }
        cout << v << "\n";
    }
}