2013年11月3日 星期日

[USACO][Serching] 1-4-4 Mother's Milk


/*
ID: 551100k1
LANG: C++
TASK: milk3
*/
#include<stdio.h>
#include<queue>
using namespace std;
struct P{
    int x,y,z;
}in,out;
int s[25][25][25]={0},is[25]={0};
queue<P> que;
int main(){
    freopen("milk3.in","r",stdin);
    freopen("milk3.out","w",stdout);
    int i,j,f=0,a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    s[0][0][c]=1;
    is[c]=1;
    que.push((P){0,0,c});
    while(que.size()){
        out=que.front();
        que.pop();
        if(out.x && out.y<b){
            in=out;
            if(in.x-b+in.y<0) in.y+=in.x,in.x=0; else
            in.x-=b-in.y,in.y=b;
            if(s[in.x][in.y][in.z]==0){
                s[in.x][in.y][in.z]=1;
                if(!in.x) is[in.z]=1;
                que.push(in);
            }
        }
        if(out.x && out.z<c){
            in=out;
            if(in.x-c+in.z<0) in.z+=in.x,in.x=0; else
            in.x-=c-in.z,in.z=c;
            if(s[in.x][in.y][in.z]==0){
                s[in.x][in.y][in.z]=1;
                if(!in.x) is[in.z]=1;
                que.push(in);
            }
        }
        if(out.y && out.x<a){
            in=out;
            if(in.y-a+in.x<0) in.x+=in.y,in.y=0; else
            in.y-=a-in.x,in.x=a;
            if(s[in.x][in.y][in.z]==0){
                s[in.x][in.y][in.z]=1;
                if(!in.x) is[in.z]=1;
                que.push(in);
            }
        }
        if(out.y && out.z<c){
            in=out;
            if(in.y-c+in.z<0) in.z+=in.y,in.y=0; else
            in.y-=c-in.z,in.z=c;
            if(s[in.x][in.y][in.z]==0){
                s[in.x][in.y][in.z]=1;
                if(!in.x) is[in.z]=1;
                que.push(in);
            }
        }
        if(out.z && out.x<a){
            in=out;
            if(in.z-a+in.x<0) in.x+=in.z,in.z=0; else
            in.z-=a-in.x,in.x=a;
            if(s[in.x][in.y][in.z]==0){
                s[in.x][in.y][in.z]=1;
                if(!in.x) is[in.z]=1;
                que.push(in);
            }
        }
        if(out.z && out.y<c){
            in=out;
            if(in.z-b+in.y<0) in.y+=in.z,in.z=0; else
            in.z-=b-in.y,in.y=b;
            if(s[in.x][in.y][in.z]==0){
                s[in.x][in.y][in.z]=1;
                if(!in.x) is[in.z]=1;
                que.push(in);
            }
        }

    }
    for(i=0;i<=c;i++){
        if(is[i]){
            if(f==0)
                f=1,printf("%d",i);
            else printf(" %d",i);
        }
    }puts("");

}

沒有留言:

張貼留言