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
#include <cstdio>
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
#define INF 999
using namespace std;

int z, n, dist[405][405], max_dist[405];
char buff[405];

int main() {
    scanf("%d", &z);
    while(z--) {

        // Read input
        scanf("%d", &n);
        FOR(y,0,n) {
            scanf("%s", buff);
            FOR(x,0,n) {
                dist[y][x] = INF;
                if (x == y) dist[y][x] = 0;
                if (buff[x] == '1') dist[y][x] = 1;
            }
        }

        // Calculate min. distance table
        FOR(u,0,n) {
            FOR(x,0,n-1) {
                FOR(y,x+1,n) {
                    if (dist[x][y] > dist[x][u] + dist[u][y]) {
                        dist[x][y] = dist[y][x] = dist[x][u] + dist[u][y];
                    }
                }
            }
        }
        FOR(x,0,n) {
            max_dist[x] = 0;
            FOR(y,0,n) if (max_dist[x] < dist[x][y]) max_dist[x] = dist[x][y];
        }

        // Check every position of teleport A-B
        int result = INF;
        FOR(A,0,n-1) FOR(B,A+1,n) {
            int local_result = 0;
            bool stop = false;
            FOR(x,0,n-1) {
                if (max_dist[x] <= local_result) continue;
                FOR(y,x+1,n) {
                    if (max_dist[y] <= local_result) continue;
                    int new_dist = dist[x][y];
                    if (new_dist > dist[x][A] + dist[B][y]) new_dist = dist[x][A] + dist[B][y];
                    if (new_dist > dist[x][B] + dist[A][y]) new_dist = dist[x][B] + dist[A][y];
                    if (result <= new_dist) { stop = true; break; }
                    if (local_result < new_dist) local_result = new_dist;
                }
                if (stop) break;
            }
            if (!stop && result > local_result) result = local_result;
        }

        printf("%d\n", result);
    }
}