2.txt

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

Source

Problem Id:1038  User Id:daofeng 
Memory:944K  Time:57358MS 
Language:C++  Result:Accepted

Source 
#include <iostream.h> 
void main() 
{ 
    int b[201][11],a[4][59050]; 
    int c[11]={1,3,9,27,81,243,729,2187,6561,19683,59049}; 
    int d,n,m,k,count,i,j,l0,x,y,sum1,sum2,cy,cy1,cy2,k1,k2,k3,i1,i2; 
    cin>>d; 
    for(count=0;count<d;count++) 
    { 
        cin>>n>>m>>k; 
        for(i=0;i<m;i++) 
            for(j=0;j<n;j++) 
                b[j][i]=0; 
        for(i=0;i<k;i++) 
        { 
            cin>>x>>y; 
            b[x-1][y-1]=1; 
        } 
        l0=c[m]; 
        for(i=0;i<4;i++) 
            for(j=0;j<l0;j++) 
                a[i][j]=0; 
        x=1;y=0;k=0; 
        while(x!=n) 
        { 
            if(k==4) k=0; 
            if (y>0&&x>1) sum1=b[x][y]+b[x][y-1]+b[x-1][y]+b[x-1][y-1]+b[x-2][y]+b[x-2][y-1]; 
            else sum1=1; 
            if (y>1&&x>0) sum2=b[x][y]+b[x][y-1]+b[x][y-2]+b[x-1][y]+b[x-1][y-1]+b[x-1][y-2]; 
            else sum2=1; 
            k1=(k+3)%4; 
            k2=(k+2)%4; 
            k3=(k+1)%4; 
            i1=2*c[y]+2*c[y-1]; 
            i2=c[y]+c[y-1]+c[y-2]; 
            for(i=0;i<l0;i++) 
            { 
                cy=(i%c[y+1])/c[y]; 
                if (cy>0) 
                { 
                    a[k][i]=a[k1][i-c[y]]; 
                } else { 
                    a[k][i]=a[k1][i]; 
                    if (sum1==0) 
                    { 
                        if (y>0) cy1=(i%c[y])/c[y-1]; 
                        else cy1=1; 
                        if (cy1==0){ 
                            if (a[k][i]<a[k2][i+i1]+1) 
                                a[k][i]=a[k2][i+i1]+1; 
                            if (sum2==0) 
                            { 
                                if (y>1) cy2=(i%c[y-1])/c[y-2]; 
                                else cy2=1; 
                                if(cy2==0){ 
                                    if (a[k][i]<a[k3][i+i2]+1) 
                                        a[k][i]=a[k3][i+i2]+1; 
                                } 
                            } 
                        } 
                    } else if (sum2==0) { 
                        if (y>0) cy1=(i%c[y])/c[y-1]; 
                        else cy1=1; 
                        if (cy1==0){ 
                            if (y>1) cy2=(i%c[y-1])/c[y-2]; 
                            else cy2=1; 
                            if(cy2==0){ 
                                if (a[k][i]<a[k3][i+i2]+1) 
                                    a[k][i]=a[k3][i+i2]+1; 
                            } 
                        } 
                    } 
                } 
            } 
            y++; 
            k++; 
            if(y==m) { 
                y=0; 
                x++; 
            } 
        } 
        cout<<a[(k+3)%4][0]<<endl; 
    } 
}