牛客网暑期ACM多校训练营（第四场）F（Beautiful Garden)

本文主要是介绍牛客网暑期ACM多校训练营（第四场）F（Beautiful Garden)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
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.

输入

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的花园，问从中加一个矩形水池令花园成为一个全对称的图形，问有多少种放法。（n和m都是偶数）

思路：暴力模拟，就是判断(x,y),(x,n-y+1),(n-x+1，y),(n-x+1,n-y+1)这四个点是否不同，分别找尽可能x与y小的值。然后x*y就是了。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2010;
int n,m,k;
int a[maxn],sum[maxn];
int c[maxn];
int ans,ct,cnt,tmp,flag;
char s[maxn][maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%s",s[i]);
ll ans=0; flag=1;
int h=2,l=2;
double d1=(double)(n-1)/2.0,d2=(double)(m-1)/2.0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
{
if(s[i][j]!=s[i][m-j-1])
{
double x=(fabs(j-d2)+0.5)*2.0;
l=max(l,(int)x);
}
if(s[i][j]!=s[n-i-1][j])
{
double x=(fabs(i-d1)+0.5)*2.0;
h=max(h,(int)x);
}
}
}
ans=(ll)((n-h)/2)*(ll)((m-l)/2);
printf("%lld\n",ans);
}
return 0;
}