1.txt

C++经典算法.rar很经典的

Source

Problem Id:1038  User Id:bobpkuhj 
Memory:952K  Time:77799MS 
Language:C  Result:Accepted

Source 
#include<stdio.h> 
#include<stdlib.h> 
main() 
{ 
    int a[4][60000],plate[150][10],d,n,m,k,index,i,j,x,y,base[11],a0; 
    base[0]=1; 
    for(i=1;i<=10;i++) 
        base[i]=base[i-1]*3; 
    scanf("%d",&d); 
    for(index=0;index<d;index++) 
    { 
        scanf("\n%d %d %d",&n,&m,&k); 
        for(i=0;i<n;i++) 
            for(j=0;j<m;j++) 
                plate[i][j]=1; 
        for(i=0;i<k;i++) 
        { 
            scanf("\n%d %d",&x,&y); 
            plate[x-1][y-1]=0; 
        } 
        if(n==1){printf("0\n");continue;} 
        for(i=1;i<4;i++) 
            for(j=0;j<base[m];j++) 
                a[i][j]=0; 
        for(x=1;x<n;x++) 
            for(y=0;y<m;y++) 
            { 
                i=((x-1)*m+y)%4; 
                for(j=0;j<base[m];j++) 
                    if((j/base[y])%3!=0) 
                        a[i][j]=a[i>0?(i-1):(i+3)][j-base[y]]; 
                    else 
                    { 
                        a[i][j]=a[i>0?(i-1):(i+3)][j]; 
                        if(x>=2&&y>=1&&(j/base[y-1])%3==0&&plate[x-2][y-1]!=0&&plate[x-1][y-1]!=0&&plate[x][y-1]!=0&&plate[x-2][y]!=0&&plate[x-1][y]!=0&&plate[x][y]!=0) 
                        { 
                            a0=a[i>1?(i-2):(i+2)][j+2*base[y]+2*base[y-1]]+1; 
                            if(a0>a[i][j]) 
                                a[i][j]=a0; 
                        } 
                        if(x>=1&&y>=2&&(j/base[y-1])%3==0&&(j/base[y-2])%3==0&&plate[x-1][y]!=0&&plate[x-1][y-1]!=0&&plate[x-1][y-2]!=0&&plate[x][y]!=0&&plate[x][y-1]!=0&&plate[x][y-2]!=0) 
                        { 
                            a0=a[i>2?(i-3):(i+1)][j+base[y]+base[y-1]+base[y-2]]+1; 
                            if(a0>a[i][j]) 
                                a[i][j]=a0; 
                        } 
                    } 
            } 
        printf("%d\n",a[i][0]); 
    } 
    exit(0); 
}