欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客网暑期ACM多校训练营(第四场)F

程序员文章站 2022-04-02 22:13:02
...

题意:

n x m的矩形,选个p x q的矩形去掉,两个矩形中⼼重合,去掉后的矩形上下左右对称
 求(p, q)⽅方案数
 n, m <= 2000, n, m是偶数,p < n 且 q < m

分析:

直接求对称的外框有多宽多长, 答案就是长*宽

#include<bits/stdc++.h>
using namespace std;
char a[2010][2010];
int main()
{
   int t,n,m;
   cin>>t;
   while(t--)
   {
      cin>>n>>m;
      int i,j;
      for(i=0;i<n;i++)
        scanf("%s",&a[i]);
        int flag=0;
        int x,y=0;
        for(i=0;i<n/2;i++)
        {
          for(j=0;j<m;j++)
          {
            //cout<<i<<" "<<j<<" ";
            //cout<<a[i][j]<<" "<<a[n-i-1][j]<<endl;
            if(a[i][j]!=a[n-i-1][j])
            {
              flag=1;
              break;
            }
          }
          if(flag==1)
                break;
        }
        x=i;
        if(i==n/2)
         x--;
        //cout<<x<<endl;
 
        flag=0;
        for(i=0;i<m/2;i++)
        {
           for(j=0;j<n;j++){
           //cout<<j<<" "<<i<<" ";
           //cout<<a[j][i]<<" "<<a[j][m-1-i]<<endl;
           if(a[j][i]!=a[j][m-1-i])
            {
                flag=1;
                break;
            }
           }
            if(flag==1)
                break;
        }
        y=i;
        if(i==m/2)
        y--;
        //cout<<y<<endl;
        cout<<x*y<<endl;
   }
    return 0;
}
/*
3
6 8
acbbbbca
dcaccacd
cdaddadc
cdaddadc
dcaccacd
acbbbbca
6 8
acbcbbca
dcaccacd
cdaddadc
cdaddadc
dcaccacd
acbbbbca
6 8
acbbbbca
dcadcacd
cdaddadc
cdaddadc
dcaccacd
acbbbbca
*/