链接：https://www.nowcoder.com/acm/contest/142/F
来源：牛客网
题目描述
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
输入
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均为偶数（even）且p<n,q<m
解题思路：对称的行之间比较，单列之间内部比较，看是否对称，记录不对称的最大宽度是maxw和不对称的行的位置maxp（下标从0开始，且只记录上半部分），答案即为[w,m)之间偶数的个数x与maxp的乘积。（比如pos为1，长的方案就只有一种情况，pos为2，那长的方案有两种情况）
有几个情况需要考虑：
1、maxw=m或者maxp=0（即最大不对称的宽度是m或者从第一行开始就不对称，包括第一行和最后一行不对称，第一行内部不对称这两种情况）
此时输出0；
2、该n*m矩阵本身就为上下对称，左右对称，则令maxw=2，maxp=n/2-1；
普通情况举例如下：（红线为maxw，紫线为宽的几种选择方案,x=3，蓝线为长的选择方案，此时i=1，则长的选择方案只有一种）所以答案为1*3
自己写的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 2010
using namespace std;
char s[maxn][maxn];
int main()
{
// freopen("C:\\Users\\dell1\\Desktop\\in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int n,m,i,j,k,w,p,x=0,y=0;
int WIDTH,POS;
bool flag=true;
scanf("%d%d",&n,&m);
int maxw=0,maxp=n;
for(i=0;i<n;i++)
scanf("%s",s[i]);
for(i=0;i<(n/2);i++)//对称的行之间是否相同
{
WIDTH=0;
if(strcmp(s[i],s[n-1-i])!=0)//对称的行不相等
{
POS=i;
for(j=0;j<(m/2);j++)
{
if(s[i][j]!=s[n-1-i][j])
WIDTH=m-2*j;
}
maxw=max(maxw,WIDTH);
maxp=min(POS,maxp);
}
}
for(i=0;i<n;i++)//对称的列是否同
{
for(j=0;j<(m/2);j++)
{
if(s[i][j]!=s[i][m-1-j])
{
WIDTH=m-2*j;
maxw=max(maxw,WIDTH);
if(i<(m/2)) POS=i;
else POS=n-1-i;
maxp=min(maxp,POS);
break;
}
}
}
if(maxp==0||maxw==m)
{
puts("0");
continue;
}
if(maxw==0) maxw+=2;//没有遇到不相等的
for(i=m-2;i>=maxw;i-=2)
x++;
if(maxp==n) y=n/2-1;//没有遇到不同的
else y=maxp;
printf("%d\n",x*y);
}
return 0;
}
看了开局20分钟左右的大佬写的代码之后，真的觉得自己写写的太复杂了，我的想法中x的求解可以再优化一下，而且不需要行与行之间比较，再列之内比较，看s[i][j]与其对应位置上的点的内容是否相同。
代码：
char s[2005][2005];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%s",s[i]+1);
int ox=n/2,oy=m/2;
for (int i=1;i<=n/2;i++)
for (int j=1;j<=m/2;j++)
if (s[i][j]!=s[n-i+1][j]||s[i][j]!=s[i][m-j+1]||s[n-i+1][m-j+1]!=s[i][j])
{
ox=min(i,ox); oy=min(j,oy);
}
int ans=(ox-1)*(oy-1);
printf("%d\n",ans);
}
return 0;
} 注意：因为只比了一半（左一半和上一半），所以还要判断其点对称位置上的值是否相同（相当于在比较下半部分），否则代码样例只通过50%
如下情况：如果只比较左下的a和右上的a，结果会错误，虽然样例过了
京公网安备 11010502036488号