#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=(a);i<(n);i++) #define per(i,a,n) for (int i=(n)-1;i>=(a);i--) #define pb push_back #define eb emplace_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef basic_string<int> BI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(1234); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=410; int n,g[N][N]; char s[N]; bitset<N> bs[N][N]; VI vec[N]; void solve() { scanf("%d",&n); rep(i,0,n) rep(j,0,n) g[i][j]=(i==j)?0:n+1; rep(i,0,n) { scanf("%s",s); rep(j,0,n) if (s[j]=='1') g[i][j]=1; } rep(k,0,n) rep(i,0,n) rep(j,0,n) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); int ans=0; rep(i,0,n) rep(j,i+1,n) ans=max(ans,g[i][j]); rep(i,0,n) { bs[i][n].reset(); rep(d,0,n) vec[d].clear(); rep(j,0,n) vec[g[i][j]].pb(j); per(d,0,n) { bs[i][d]=bs[i][d+1]; for (auto x:vec[d]) bs[i][d][x]=1; } } rep(i,0,n) rep(j,i+1,n) { auto check=[&](int w) { if (w<=0) return false; rep(x,0,n) { if ((bs[x][w+1]&bs[j][max(w+1-g[x][i],0)]&bs[i][max(w+1-g[x][j],0)]).any()) return false; } return true; }; while (check(ans-1)) --ans; } printf("%d\n",ans); } int _; int main() { for (scanf("%d",&_);_;_--) { solve(); } }
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 | #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=(a);i<(n);i++) #define per(i,a,n) for (int i=(n)-1;i>=(a);i--) #define pb push_back #define eb emplace_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef basic_string<int> BI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(1234); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=410; int n,g[N][N]; char s[N]; bitset<N> bs[N][N]; VI vec[N]; void solve() { scanf("%d",&n); rep(i,0,n) rep(j,0,n) g[i][j]=(i==j)?0:n+1; rep(i,0,n) { scanf("%s",s); rep(j,0,n) if (s[j]=='1') g[i][j]=1; } rep(k,0,n) rep(i,0,n) rep(j,0,n) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); int ans=0; rep(i,0,n) rep(j,i+1,n) ans=max(ans,g[i][j]); rep(i,0,n) { bs[i][n].reset(); rep(d,0,n) vec[d].clear(); rep(j,0,n) vec[g[i][j]].pb(j); per(d,0,n) { bs[i][d]=bs[i][d+1]; for (auto x:vec[d]) bs[i][d][x]=1; } } rep(i,0,n) rep(j,i+1,n) { auto check=[&](int w) { if (w<=0) return false; rep(x,0,n) { if ((bs[x][w+1]&bs[j][max(w+1-g[x][i],0)]&bs[i][max(w+1-g[x][j],0)]).any()) return false; } return true; }; while (check(ans-1)) --ans; } printf("%d\n",ans); } int _; int main() { for (scanf("%d",&_);_;_--) { solve(); } } |