三個水杯

時間限制：1000 ms ?|? 內存限制：65535 KB 難度：4 描述

給出三個水杯，大小不一，并且只有最大的水杯的水是裝滿的，其余兩個為空杯子。三個水杯之間相互倒水，并且水杯沒有標識，只能根據給出的水杯體積來計算。現在要求你寫出一個程序，使其輸出使初始狀態到達目標狀態的最少次數。

輸入

第一行一個整數N(0<N<50)表示N組測試數據
接下來每組測試數據有兩行，第一行給出三個整數V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三個水杯的體積。
第二行給出三個整數E1 E2 E3 （體積小于等于相應水杯體積）表示我們需要的最終狀態

輸出

每行輸出相應測試數據最少的倒水次數。如果達不到目標狀態輸出-1

樣例輸入

2 6 3 1 4 1 1 9 3 2 7 1 1

樣例輸出

3 -1 View Code #include<stdio.h> #include<queue> #include<string.h> using namespace std; struct node {int c[3];int move[3]; int step; }; int visit[1010100];int hash(node a) { return (a.move[1]*10000+a.move[1]*100+a.move[2]*10); }int judge(node a,node b) {return (a.move[0]==b.move[0]&&a.move[1]==b.move[1]&&a.move[2]==b.move[2]); }int main() {int x,i,j,min,ok;node begin,end;queue<node>s;scanf("%d",&x);while(x--){scanf("%d%d%d",&begin.c[0],&begin.c[1],&begin.c[2]);begin.move[0]=begin.c[0];begin.move[1]=begin.move[2]=0;begin.step=0;s.push(begin);scanf("%d%d%d",&end.move[0],&end.move[1],&end.move[2]); //后面是判定move數組ok=0;memset(visit,0,sizeof(visit));visit[hash(begin)]=1;while(!s.empty()){node u=s.front();s.pop();if(judge(u,end)){printf("%d\n",u.step);ok=1;break;}for(i=0;i<3;i++)//從i倒到jfor(j=0;j<3;j++)if(i!=j){min=u.c[j]-u.move[j];if(u.move[i]<min)min=u.move[i];node v=u;v.move[i]-=min;v.move[j]+=min;v.step++;if(!visit[hash(v)]){visit[hash(v)]=1;s.push(v);}}}if(!ok)printf("-1\n");while(!s.empty())s.pop();}return 0; }

本題主要是用BFS搜索各種情況，用隊列存貯狀態，直到搜到所要答案。以后這種情況很多的類型，相互變換的都可以用BFS嘗試下

轉載于:https://www.cnblogs.com/zibuyu/archive/2013/03/13/2957290.html

總結

以上是生活随笔為你收集整理的nyoj 21 三个水杯 BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。