洛谷 P1432 倒水問題

目錄

• 題目
• 思路
• $Code$

題目

戳

思路

$bfs$
第一遍提交$50$，第二遍就$100$了,qwq

$Code$

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
int t,ca,cb,n,step,sum;
int a_now[100001],b_now[100001],flag[100001];//a_now、b_now分別記錄a、b壺中的水，flag判斷當前這一步是從哪裡擴展來的
int ans[100001],qwq[100001];//ans存儲進行了哪一步操作，qwq是最後的答案
bool vis[1001][1001];//判斷是否到達過當前情況
inline int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}//讀優
inline void write(int x){
    if(x<0) putchar('-'),write(-x);
    else {if(x/10)write(x/10);putchar(x%10+'0');}
}//輸出
void js(int x){
    if(flag[x]){
        js(flag[x]),step++;
        qwq[++sum]=ans[x];
    }
    return;
}//計算用了幾步以及分別是那幾步
void bfs(int a,int b){
    int head=0,tail=1;
    flag[tail]=0;
    a_now[tail]=a;
    b_now[tail]=b;
    vis[a][b]=1;
    while(head<tail){
        head++;
        for(register int i=1;i<=6;++i){
            if(i==1){
                int c=ca,d=b_now[head];
                if(!vis[c][d]){
                    vis[c][d]=1;
                    tail++,ans[tail]=i;
                    a_now[tail]=c,b_now[tail]=d;
                    flag[tail]=head;
                    if(d==n){js(tail);return;}
                }
            }//1操作:fillA 意為給A灌滿水
            if(i==2){
                int c=a_now[head],d=cb;
                if(!vis[c][d]){
                    vis[c][d]=1;
                    tail++,ans[tail]=i;
                    a_now[tail]=c,b_now[tail]=d;
                    flag[tail]=head;
                    if(d==n){js(tail);return;}
                }
            }//2操作:fill B
            if(i==3){
                int c=0,d=b_now[head];
                if(!vis[c][d]){
                    vis[c][d]=1;
                    tail++,ans[tail]=i;
                    a_now[tail]=c,b_now[tail]=d;
                    flag[tail]=head;
                    if(d==n){js(tail);return;}
                }
            }//3操作:empty A 意為將A中水倒空
            if(i==4){
                int c=a_now[head],d=0;
                if(!vis[c][d]){
                    vis[c][d]=1;
                    tail++,ans[tail]=i;
                    a_now[tail]=c,b_now[tail]=d;
                    flag[tail]=head;
                    if(d==n){js(tail);return;}
                }
            }//4操作:empty B
            if(i==5){
                int c,d,cha=ca-a_now[head];
                if(cha>=b_now[head]) d=0,c=a_now[head]+b_now[head];
                else c=ca,d=b_now[head]-cha;
                if(!vis[c][d]){
                    vis[c][d]=1;
                    tail++,ans[tail]=i;
                    a_now[tail]=c,b_now[tail]=d;
                    flag[tail]=head;
                    if(d==n){
                        js(tail);
                        return;
                    }
                }
            }//5操作:pour BA 意為將B中水倒到A中（直到A滿或者B中水沒有剩餘）
            if(i==6){
                int c,d;
                int cha=cb-b_now[head];
                if(cha>=a_now[head]) c=0,d=b_now[head]+a_now[head];
                else c=a_now[head]-cha,d=cb;
                if(!vis[c][d]){
                    vis[c][d]=1;
                    tail++,ans[tail]=i;
                    a_now[tail]=c;
                    b_now[tail]=d;
                    flag[tail]=head;
                    if(d==n){
                        js(tail);
                        return;
                    }
                }
            }//6操作:pour A B
        }
    }
}
int main(){
    t=read();
    while(t--){
        ca=read(),cb=read(),n=read();
        bfs(0,0);//搜索
        printf("%d ",step);//輸出有幾步
        for(register int i=1;i<=step;++i){//輸出答案
            write(qwq[i]);
            printf(" ");
            //printf("%d ",qwq[i]);
        }
        puts("");//換行
        step=sum=0;
        memset(vis,0,sizeof(vis));//初始化
    }
    return 0;
}