牛客多校第四场 F Beautiful Garden

Beautiful Garden

问题分析

问，在保证花园对称的情况下，在花园*(不能涉及边界)建造对称水池的方案数。
假设矩阵上下左右是完全对称的，大小为n×m$n\times m$，那么方案数由乘法原理不难推出是ans=n−12×m−12$ans=\frac{n-1}{2}\times \frac{m-1}{2}$。

因为是上下左右对称的，所以我们只需要考虑矩阵的n2×m2$\frac{n}{2}\times \frac{m}{2}$即可。

就拿样例1$1$来说，6×8$6\times 8$的矩阵，我们以左上角建坐标系的话，可选宽度为{2,4}$\{2,4\}$，化为可选y$y$坐标就是{1,2}$\{1,2\}$,可选长度为{2,4,6}$\{2,4,6\}$，化为可选x$x$坐标就是{1,2,3}$\{1,2,3\}$，可用的方案数为(2×2),(2×4),(2×6),(4×2),(4×4),(4×6)$(2\times 2),(2\times 4),(2\times 6),(4\times 2),(4\times 4),(4\times 6)$,但是如果有不对称的点，那么我们所建造的水池必须要覆盖这个点。拿样例3$3$来说，不对称点为(1,3)$(1,3)$，就是可选的y$y$坐标2$2$不可用了，但是不影响可选的x$x$坐标，因为可以正好覆盖(1,3)$(1,3)$点，所以方案数为1×3=3$1\times 3=3$。

#include<bits/stdc++.h>
using namespace std;
const int N = 2002;
char a[N][N];

int main() 
{
    //freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i) {
            scanf("%s", a[i]);
        }
        int x = (n - 1) / 2, y = (m - 1) / 2;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < m / 2; ++j) {
                if (a[i][j] != a[n - i - 1][j] || a[i][j] != a[i][m - j - 1] || a[i][j] != a[n - i - 1][m - j - 1]) {
                    x = min(x, i);
                    y = min(y, j);
                }
            }
        }
        printf("%d\n", x * y);
    }
    return 0;
}