HDU 4618 - Palindrome Sub-Array（2013MUTC2-1008）（DP）

d（i，j，k）表示左上角坐标为（i，j），k为正方形边长

d（i，j，k）=1，如果d（i+1，j+1，k-2）=0，且上下两个外围的相等且回文，左右两个外围的相等且回文；否则d（i，j，k）=0

d（i，j，0）=1

d（i，j，1）=1

#include <stdio.h>

#include <string.h>

int a[310][310];

bool d[310][310][310];

int check(int x,int y,int l)

{

    for(int i=y;i<=y+l-1;i++)

    if(a[x][i]!=a[x+l-1][i])return 0;

     for(int i=x;i<=x+l-1;i++)

    if(a[i][y]!=a[i][y+l-1])return 0;

    for(int i=x;i<=x+l/2;i++)

    if(a[i][y]!=a[x+l-1-(i-x)][y])return 0;

    for(int i=y;i<=y+l/2;i++)

    if(a[x][i]!=a[x][y+l-1-(i-y)])return 0;

    return 1;

}

int main()

{

    int T;

    int n,m;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        memset(d,0,sizeof(d));

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=m;j++)

            {

                scanf("%d",&a[i][j]);

                d[i][j][0]=1;

                d[i][j][1]=1;

            }

        }

        int l=n<m?n:m;

        int ans=1;

        for(int k=2;k<=l;k++)

        {

            for(int i=1;i<=n;i++)

            {

                if(i+k-1>n)break;

                for(int j=1;j<=m;j++)

                {

                    if(j+k-1>m)break;

                    if(d[i+1][j+1][k-2]&&check(i,j,k))

                    {

                        d[i][j][k]=1;

                        if(k>ans)ans=k;

                    }

                }

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}