TIOJ 1099 B.射手座之日 [BFS] [NPSC 2006]

poao899    1099    Accepted    24048K    10281MS    G++    1.83K    2010-04-02 10:18:25                 .



本來想寫Bi-BFS的但好像寫炸了

            x+y+z= k            這個剪枝太強大了











//*****************************************************

#include<stdio.h>
#define QLEN 2000000
bool chk[3010][3010][2], can;
int q[QLEN][3], front, rear;
int n, x1, y1, z1, x2, y2, z2, sum, a, b, t1, t2, aa[3];
inline int max2(int i, int j, int k, int &m1, int &m2){
    int max=(i>j)?(i>k?i:k):(j>k?j:k), min=(i<j)?(i<k?i:k):(j<k?j:k);
    m1= min; m2= i+j+k-max-min;
}
inline void push(int x, int y, int op){
    if(x>=0&&x<=n&&y>=0&&y<=n&&(sum-x-y)>=0&&(sum-x-y)<=n){
        if(chk[x][y][!op]){can=1; return;}
        if(!chk[x][y][op]){
            chk[x][y][op]= 1;
            q[rear][0]= x; q[rear][1]= y; q[rear][2]= op;
            rear= ++rear%QLEN;
        }
    }
}
int main(){
    while(~scanf("%d%d%d%d%d%d%d", &n, &x1, &y1, &z1, &x2, &y2, &z2), n){
        if(x1+y1+z1!= x2+y2+z2){puts("No"); continue;}
        sum= x1+y1+z1;
        for(int i=0; i<=n; i++)
            for(int j=0; j<=n; j++)
                chk[i][j][0]= chk[i][j][1]= 0;
        front=0; rear=2; can=0;
        max2(x1,y1,z1,q[0][0],q[0][1]); q[0][2]= 0;
        max2(x2,y2,z2,q[1][0],q[1][1]); q[1][2]= 1;
        chk[q[0][0]][q[0][1]][0]= chk[q[1][0]][q[1][1]][1]= 1;
        while(!can&& front!=rear){
            int x= q[front][0], y= q[front][1], opt= q[front][2];
            if(chk[x][y][!opt]){can=1; break;}
            aa[0]= x; aa[1]= y; aa[2]= sum-x-y;
            if(opt==0){
                for(int i=0; i<3; i++)
                    for(int j=0; j<3; j++){
                        if(i==j)continue;
                        x=aa[i]; y=aa[j];
                        t1= (y*2)-x+1; t2= (x*2)-y-1;
                        max2(t1, t2, sum-t1-t2, a, b);
                        push(a, b, opt);
                    }
            }else{
                for(int i=0; i<3; i++)
                    for(int j=0; j<3; j++){
                        if(i==j)continue;
                        x=aa[i]; y=aa[j];
                        t1= (x*2)+y+1; t2= (y*2)+x-1;
                        if(t1%3==0 && t2%3==0){
                            t1/=3; t2/=3;
                            max2(t1, t2, sum-t1-t2, a, b);
                            push(a, b, opt);
                        }
                    }
            }
            front= ++front%QLEN;
        }
        if(can)puts("Yes");
        else puts("No");
    }
}