Demo entry 6762978

hard

   

Submitted by 反对法 on Oct 18, 2018 at 09:55
Language: C++. Code size: 2.2 kB.

#include <bits/stdc++.h>
using namespace std;

int b[3],bound[3];
// 倒油的6种可能
int x[]={0,0,1,1,2,2};
int y[]={1,2,0,2,0,1};

struct node{
    int a[3];//记录各个桶的油量
}p;

queue<node> q;
const int N=110;
int vis[N][N][N];// vis[i][j][k] 记录 S桶有i L油,
                                //    x桶有j L油
                                //    y桶有k L油
                                // 从开始倒成这局面,需要的步数
int bfs(){
	
    p.a[0]=bound[0]; // p 表示 "S桶装满,x、y桶现在还是0 L"
                     // 初始状态
                     
    q.push(p);
    vis[p.a[0]][p.a[1]][p.a[2]]=0;

    int ans=-1;
    while(!q.empty()){
    	// 取队首元素,并出队 
        p=q.front();
        q.pop();
        
        // 判断是否已经分好,若已经分好,则跳出循环 
        for(int i=0;i<3;++i)
            b[i]=p.a[i];  
        sort(b,b+3);
        if(b[0]==0&&b[1]==b[2]){
            ans=vis[p.a[0]][p.a[1]][p.a[2]];
            break;
        }
        
        // x[i] ---> y[i]  从x[i] 桶里 倒油 进 桶y[i] 
        for(int i=0;i<6;++i){
            int tx=p.a[x[i]],ty=p.a[y[i]];
            // 桶x[i] 是空的或者 y[i] 是满的, 则不用倒 
            if(tx==0||ty==bound[y[i]]) continue;
            
            //倒 有两种情况
            // 1、 x[i]桶的油全倒进去(两桶的油之和不会溢出)
            // 2、 x[i]桶的油倒进去部分,y[i]桶 已经满了
            if(tx+ty<=bound[y[i]]){
                ty+=tx;
                tx=0;
            }else{
                tx-=bound[y[i]]-ty;
                ty=bound[y[i]];
            
            }
            // 倒完此次,会出现新的局面
            node tmp;
            for(int j=0;j<3;++j)
                tmp.a[j]=p.a[j];
            tmp.a[x[i]]=tx;
            tmp.a[y[i]]=ty;
            
            int &v=vis[tmp.a[0]][tmp.a[1]][tmp.a[2]];
            if(v!=-1) continue;// 前面倒成过这样,这个不用做了
                              // 防止重复倒来倒去
            v=vis[p.a[0]][p.a[1]][p.a[2]]+1;
            q.push(tmp);
        }
    }
    
    
    if(ans==-1) printf("NO\n");
    else printf("%d\n",ans);

}                                

int main(){
	memset(vis,-1,sizeof vis);
    for(int i=0;i<3;++i){
        scanf("%d",&bound[i]);//桶的容量 顺序 S、x、y
        p.a[i]=0;
    }
    bfs();
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).