3.txt

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

Source

Problem Id:1038  User Id:hawk 
Memory:824K  Time:8439MS 
Language:C++  Result:Accepted

Source 
/* 
hawking@pku 
*/ 
#include<stdio.h> 
int n,m,k,D,e[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049},mmax,blank[10],x,y,curr,tt,a1,a2,i,j,p; 
bool b[150][10],can1,can2; 
unsigned char c[4][59049],bit[11][59049],*l0,*l1,*l2,*l3,*bit0,*bit1,*bit2; 
void main() 
{ 
    scanf("%d",&D); 
    for(p=0;p<59049;p++)for(tt=p,i=0;i<11&&tt>0;i++,tt/=3)bit[i][p]=tt%3; 
    while(D--) 
    { 
        scanf("%d %d %d",&n,&m,&k); 
        curr=2; 
        mmax=e[m]; 
        for(i=0;i<4;i++)for(j=0;j<mmax;j++)c[i][j]=0; 
        for(i=0;i<n;i++)for(j=0;j<m;j++)b[i][j]=false; 
        for(i=0;i<k;i++) 
        { 
            scanf("%d %d",&x,&y); 
            b[x-1][y-1]=true; 
        } 
        for(j=0;j<m;j++)blank[j]=1-b[0][j]; 
        for(i=1;i<n;i++)for(j=0;j<m;j++) 
        { 
            curr=(curr+1)%4; 
            if(!b[i][j])blank[j]++;else blank[j]=0; 
            can1=(blank[j]>2&&blank[j-1]>2);can2=(j>1&&blank[j]>1&&blank[j-1]>1&&blank[j-2]>1); 
            l0=c[curr];l1=c[(curr+3)%4];l2=c[(curr+2)%4];l3=c[(curr+1)%4]; 
            a1=2*e[j]+2*e[j-1];a2=e[j]+e[j-1]+e[j-2]; 
            bit0=bit[j];bit1=bit[j-1];bit2=bit[j-2]; 
            for(p=0;p<mmax;p++) 
                if(bit0[p])l0[p]=l1[p-e[j]]; 
                else{ 
                    l0[p]=l1[p]; 
                    if(j&&bit1[p]==0){ 
                        if(can1&&(tt=l2[p+a1]+1)>l0[p])l0[p]=tt; 
                        if(can2&&bit2[p]==0&&(tt=l3[p+a2]+1)>l0[p])l0[p]=tt;                         
                    } 
                     
                } 
        } 
        printf("%d\n",c[curr][0]); 
    } 
}