链接：

来源：牛客网

题目描述

There's a beautiful garden whose size is n x m in Chiaki's house. The garden can be partitioned into n x m equal-sized square chunks. There are some kinds of flowers planted in each square chunk which can be represented by using lowercase letters.

However, Chiaki thinks the garden is not beautiful enough. Chiaki would like to build a water pool in the garden. So that the garden would look like symmetric (both horizontally and vertically). The water pool is a rectangle whose size is p x q and the center of the water pool is also the center of the garden.

Something else important you should know is:

• n, m, p and q are all even.
• p is always less than n.
• q is always less than m.
• The borders of the water pool are parallel to the border of garden.

Chiaki would like to know the number of different pairs of (p, q) she can choose.

输入描述:

There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 100) indicating the number of test cases. For each test case: The first line contains two integers n and m (1 ≤ n, m ≤ 2000, n and m are even) -- the size of the garden. For next n lines, each line contains m characters showing the garden. It is guaranteed that only lowercase letters will appear.

输出描述:

For each test case, output an integer indicating the number of choices to build the water pool.

示例1

输入

36 8acbbbbcadcaccacdcdaddadccdaddadcdcaccacdacbbbbca6 8acbcbbcadcaccacdcdaddadccdaddadcdcaccacdacbbbbca6 8acbbbbcadcadcacdcdaddadccdaddadcdcaccacdacbbbbca

输出

603 题意：在一个n*m的花园，我们想要这个花园变得更加完美，也就是行对称，列对称，但是花园开始可能是不对称，也可能对称， 中间我们可以把中间的花铲走挖一个p*q池子，花园的中心就是池子的中心，来使花园看上去对称，问挖池子的方法有多少个， 而且n,m,p,q都是偶数，p

#include 
          
           using namespace std;const int N = 2E3 + 7;string s[N];int a[N], b[N];int main(){    ios::sync_with_stdio(false), cin.tie(0);    int T;    cin >> T;    while(T--)    {        int n, m;        cin >> n >> m;        for(int i = 0; i < n; i++)        {            cin >> s[i];        }        int num1 = 0, num2 = 0;        for(int i = 0; i < n/2; i++)//这里我们直接用num1作间隔，然后直接匹配字符串是否相等，实际上是匹配了列上的字符是否对称        {            if(s[i] == s[n-i-1])            {                num1++;            }            else            {                break;            }        }        for(int i = 0; i < m/2; i++)//因为行的字符不能直接用字符串相等，所以我们判断下回文        {            int flag = 1;            for(int j = 0; j < n; j++)            {                if(s[j][i] != s[j][m-i-1])                {                    flag = 0;                    break;                }            }            if(flag)            {                num2++;            }            else            {                break;            }        }        if(num1 == 0 || num2 == 0)        {            cout << 0 << endl;        }        else        {            if(num1*2 == n) num1--;//如果到了边界减一，我们不能把花园边界挖掉            if(num2*2 == m) num2--;            cout << num1*num2 << endl;//最终答案        }    } }
          

 

主要思路：模拟+贪心