链接：https://www.nowcoder.com/acm/contest/142/F
来源：牛客网
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.
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
6 0 3
题意：在一个n*m的花园，我们想要这个花园变得更加完美，也就是行对称，列对称，但是花园开始可能是不对称，也可能对称，
中间我们可以把中间的花铲走挖一个p*q池子，花园的中心就是池子的中心，来使花园看上去对称，问挖池子的方法有多少个，
而且n,m,p,q都是偶数，p<n q<m
思路：因为我们要使花园看上去对称，我们就去找从0开始最近的不对称的点在哪，行列分别去找，然后我们的池子必须涵盖最近的点，如果我们把
最近的错误点盖住就可以满足了，然后再看最近的点和边界相差多少，行列间隔的距离相乘就是答案，因为我没扩展的时候有x个，我们延伸两个的时候
，又有x个
#include <bits/stdc++.h> 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;//最终答案 } } }
主要思路：模拟+贪心
原文：https://www.cnblogs.com/Lis-/p/9383214.html