1838(想了很久的dp).cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 43 行

#include<cstdio>
char a[2001][2001];
int  b[2001][2001];
void build_b(int N){
    int i,j;
    for(i = 0;i < N;i++)
        for(j = 0;j < N;j++){
            if(i == 0||j == 0)
                b[i][j]=1;
            else if(i != 0||j != 0)
                if(a[i][j] == a[i][j-1] || a[i][j] == a[i-1][j])
                    b[i][j] = 1;
                else if(a[i][j] != a[i][j-1] && a[i][j] != a[i-1][j]){
                    b[i][j] = b[ i-1][j] < b[i][j-1] ? b[i-1][j] : b[i][j-1];
                    if(a[ i-b[i][j] ][ j-b[i][j] ] != a[ i-b[i][j]+1 ][ j-b[i][j] ] && a[ i-b[i][j] ][ j-b[i][j] ] != a[ i-b[i][j] ][ j-b[i][j]+1 ])
                        b[i][j]++;
                }
        }
}
void main()
{
    int m,i,j,N,max,count;
    scanf("%d",&m);
    while(m--){
        scanf("%d",&N);
        i=0;
        while(i<N)
            scanf("%s",a[i++]);
        build_b(N);
        max = 0;
        for(i = 0;i < N;i++)
            for(j = 0;j < N;j++)
                if(b[i][j]>0 && a[ i-b[i][j]+1 ][ j-b[i][j]+1 ] == '1' && b[i][j] > max)
                    max = b[i][j];
        count = 0;
        for(i = 0;i < N;i++)
            for(j = 0;j < N;j++)
                if(b[i][j] == max && a[ i-b[i][j]+1 ][ j-b[i][j]+1 ] == '1')
                    count++;
        printf("%d %d\n",max,count);
    }
}