#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define pb push_back #define st first #define nd second const int MAXN = 407; int dl[MAXN][MAXN]; bool krawedzie[MAXN][MAXN]; int jakie[MAXN][MAXN]; bool odw[MAXN]; void bfs(int v, int n) { int w = v; queue<pair<int, int>> q; q.push({v, 0}); while (!q.empty()) { pair<int, int> p = q.front(); q.pop(); v = p.st; if (odw[v]) { continue; } odw[v] = true; dl[w][v] = p.nd; for (int i = 1; i <= n; i++) { if (odw[i]) { continue; } if (krawedzie[v][i]) { q.push({i, p.nd + 1}); } } } } bool spr(int d, int n) { for (int a = 1; a <= n; a++) { for (int p2 = 1; p2 <= n; p2++) { jakie[a][p2] = 1e9; for (int b = 1; b <= n; b++) { if (dl[a][b] > d) { jakie[a][p2] = min(jakie[a][p2], max(0, d + 1 - dl[b][p2])); } } } } for (int p1 = 1; p1 <= n; p1++) { for (int p2 = p1 + 1; p2 <= n; p2++) { bool czy = true; for (int a = 1; a <= n; a++) { if (dl[a][p1] <= dl[a][p2]) { if (dl[a][p1] >= jakie[a][p2]) { czy = false; break; } } else { if (dl[a][p2] >= jakie[a][p1]) { czy = false; break; } } } if (czy) { return true; } } } return false; } void solve() { int n; cin >> n; rep(i, n) { string s; cin >> s; rep(j, n) { if (s[j] == '1') { krawedzie[i + 1][j + 1] = true; } else { krawedzie[i + 1][j + 1] = false; } } } for (int w = 1; w <= n; w++) { bfs(w, n); rep(i, n + 1) { odw[i] = false; } } int poc = 0; int kon = n + 1; int odp = n + 1; while (poc < kon) { int sr = (poc + kon)/2; if (spr(sr, n)) { odp = sr; kon = sr; } else { poc = sr + 1; } } cout << odp << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { solve(); } return 0; }
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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define pb push_back #define st first #define nd second const int MAXN = 407; int dl[MAXN][MAXN]; bool krawedzie[MAXN][MAXN]; int jakie[MAXN][MAXN]; bool odw[MAXN]; void bfs(int v, int n) { int w = v; queue<pair<int, int>> q; q.push({v, 0}); while (!q.empty()) { pair<int, int> p = q.front(); q.pop(); v = p.st; if (odw[v]) { continue; } odw[v] = true; dl[w][v] = p.nd; for (int i = 1; i <= n; i++) { if (odw[i]) { continue; } if (krawedzie[v][i]) { q.push({i, p.nd + 1}); } } } } bool spr(int d, int n) { for (int a = 1; a <= n; a++) { for (int p2 = 1; p2 <= n; p2++) { jakie[a][p2] = 1e9; for (int b = 1; b <= n; b++) { if (dl[a][b] > d) { jakie[a][p2] = min(jakie[a][p2], max(0, d + 1 - dl[b][p2])); } } } } for (int p1 = 1; p1 <= n; p1++) { for (int p2 = p1 + 1; p2 <= n; p2++) { bool czy = true; for (int a = 1; a <= n; a++) { if (dl[a][p1] <= dl[a][p2]) { if (dl[a][p1] >= jakie[a][p2]) { czy = false; break; } } else { if (dl[a][p2] >= jakie[a][p1]) { czy = false; break; } } } if (czy) { return true; } } } return false; } void solve() { int n; cin >> n; rep(i, n) { string s; cin >> s; rep(j, n) { if (s[j] == '1') { krawedzie[i + 1][j + 1] = true; } else { krawedzie[i + 1][j + 1] = false; } } } for (int w = 1; w <= n; w++) { bfs(w, n); rep(i, n + 1) { odw[i] = false; } } int poc = 0; int kon = n + 1; int odp = n + 1; while (poc < kon) { int sr = (poc + kon)/2; if (spr(sr, n)) { odp = sr; kon = sr; } else { poc = sr + 1; } } cout << odp << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { solve(); } return 0; } |