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
94
// Brut

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 2147483640

int t, n;

vector <int> graf[405];

int odleglosci[405];

int BFS(int w, int z1, int z2);

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while(t){
		t--;

		// Wczytywanie grafu
		cin >> n;
		for(int i=1; i<=n; i++){
			graf[i].clear();
			string edges;
			cin >> edges;
			for(int e=0; e<n; e++)
				if(edges[e] == '1'){
					//cout << i << "->" << e+1 << endl;
					graf[i].push_back(e+1);
				}
		}

		// Rozwiązanie
		int rozwiązanie = INF;
		// dla każdej złączonej pary
		for(int z1=1; z1<=n; z1++){
			for(int z2=z1+1; z2<=n; z2++){
				int max_odl = 0;
				for(int w = 1; w<=n; w++)
					max_odl = max(max_odl, BFS(w, z1, z2));
				rozwiązanie = min(rozwiązanie, max_odl);
			}
		}
		cout << rozwiązanie << "\n";
	}

	return 0;
}

int BFS(int w, int z1, int z2){
	for(int j=1; j<=n; j++)
		odleglosci[j] = INF;
	odleglosci[w] = 0;

	queue<int> q;
	q.push(w);

	while(q.size()){
		int u = q.front();
		q.pop();

		for(auto v: graf[u]){
			if(odleglosci[v] > odleglosci[u] + 1){
				odleglosci[v] = odleglosci[u] + 1;
				q.push(v);
			}
		}
		if(u == z1){
			if(odleglosci[z2] > odleglosci[u]){
				odleglosci[z2] = odleglosci[u];
				q.push(z2);
			}
		}
		if(u == z2){
			if(odleglosci[z1] > odleglosci[u]){
				odleglosci[z1] = odleglosci[u];
				q.push(z1);
			}
		}
	}
	int max_odl = 0;
	for(int i=1; i<=n; i++)
		max_odl = max(odleglosci[i], max_odl);
	return max_odl;
}