发现若 (G_{i,j}=mathsf{A})，则 (i,j) 一定在同一个强连通分量中，而同一个强连通分量中不能存在 (mathsf{X})，因此先将满足 (G_{i,j}=mathsf{A}) 的 (i,j) 进行缩点，然后通过 (mathsf{X}) 判断是否无解。
得最优情况一定是每个强连通分量内部为一个环，强连通分量之间连成一条链。那么将强连通分量之间两两合并，就能减少链上边的使用，得答案为 (n-1) 加上点数 (geqslant 2) 的强连通分量个数。
接下来就只考虑 (mathsf{X}) 边即可，因为在连通图中，若 (mathsf{A}) 或 (mathsf{X}) 满足，(mathsf{O}) 就能满足。于是问题就转化为：将所有点划分到若干强连通分量中，且这些强连通分量间无连边，最小化强连通分量个数。
发现点数 (geqslant 2) 的强连通分量只有 (23)，所以考虑状压 (DP)。设 (f(S)) 为点集 (S) 是否合法，那么其子集卷积 (k) 次后使得全集合法的最小的 (k) 即为所求。设强连通分量个数为 (cnt)，其复杂度为 (O(cnt^32^{cnt}))，无法接受。
发现若存在合法集合 (S,T)，则 (S-S cup T) 也是合法集合，因此可以用或卷积来代替子集卷积，得复杂度为 (O(cnt^22^{cnt}))。发现并不用每次都做 (FWT)，因为只需知道全集的情况即可，于是可以用公式：
来 (O(2^{cnt})) 单点求或卷积的值。于是复杂度就为 (O(cnt2^{cnt})) 了。
求 (f(S)) 时就每次向 (S-operatorname{lowbit}(S)) 中加入 (operatorname{lowbit}(S)) 即可，这里预处理出每个强连通分量和哪些强连通分量有 (mathsf{X}) 边就能快速转移。
#include<bits/stdc++.h>
#define maxn 55
#define maxs 8400010
#define lowbit(x) (x&(-x))
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,tot,all,ans;
int fa[maxn],id[maxn],siz[maxn],col[maxn],e[maxn];
int f[maxs],g[maxs],c[maxs],cnt[maxs];
bool vis[maxn];
char w[maxn][maxn];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool check()
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(w[i][j]=='X'&&find(i)==find(j))
return false;
return true;
}
int get(int s)
{
int v=0;
while(s) s>>=1,v++;
return v;
}
void FWT(int *a)
{
for(int len=1;len<=all;len<<=1)
for(int i=0;i<=all;i+=len<<1)
for(int j=i;j<i+len;++j)
a[j+len]+=a[j];
}
int main()
{
read(n);
for(int i=1;i<=n;++i) scanf("%s",w[i]+1),fa[i]=i;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(w[i][j]=='A')
fa[find(i)]=find(j);
if(!check())
{
puts("-1");
return 0;
}
for(int i=1;i<=n;++i)
{
siz[col[i]=find(i)]++;
if(vis[col[i]]) continue;
vis[col[i]]=true;
}
for(int i=1;i<=n;++i)
if(i==col[i]&&siz[i]!=1)
id[i]=++tot;
if(!tot)
{
printf("%d
",n-1);
return 0;
}
all=(1<<tot)-1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(w[i][j]!='X'||siz[col[i]]==1||siz[col[j]]==1) continue;
int x=id[col[i]],y=id[col[j]];
e[x]|=1<<(y-1),e[y]|=1<<(x-1);
}
}
f[0]=1;
for(int s=1;s<=all;++s)
{
int t=s^lowbit(s);
if(!(e[get(lowbit(s))]&s)) f[s]=f[t];
}
if(f[all])
{
printf("%d
",n);
return 0;
}
FWT(f);
for(int i=0;i<=all;++i) g[i]=f[i];
for(int i=1;i<=all;++i) cnt[i]=cnt[i-lowbit(i)]+1;
for(int i=0;i<=all;++i) c[i]=cnt[i^all]&1?-1:1;
ans=n;
while(1)
{
ans++;
for(int i=0;i<=all;++i) f[i]*=g[i];
int v=0;
for(int i=0;i<=all;++i) v+=f[i]*c[i];
if(v) break;
}
printf("%d",ans);
return 0;
}