题目描述
给出一个n*m的矩阵，矩阵中有A和Q两种字符
求有多少个子矩阵，矩阵的四个角选出三个能构成QAQ
记A为1，Q为0，当且仅当矩阵四个角和为1或2满足条件
剩下的做法和之前的洛谷P3941 入阵曲（传送门）差不多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
const int N=505;
int w[N][N],c[N],cnt[N],n,m;
LL ans=0;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
inline char get()
{
register char ch=getchar();
while (!(('a'<=ch&&ch<='z')||('A'<=ch&&ch<='Z'))) ch=getchar();
return ch;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char opt=get();
w[i][j]=opt=='A'?1:0;
}
for(int i=1;i<=m;++i)
for(int j=i+1;j<=m;++j)
{
for(int k=0;k<=4;k++) cnt[k]=0;
for(int k=1;k<=n;++k)
{
c[k]=w[k][i]+w[k][j];
ans+=cnt[2-c[k]];
if (c[k]<=1) ans+=cnt[1-c[k]];
cnt[c[k]]++;
}
}
printf("%lld",ans);
return 0;
}