首页 > 代码库 > NYOJ 21 三个水杯

NYOJ 21 三个水杯

2024-07-12 21:01:52   221人阅读

三个水杯

时间限制：1000 ms  |  内存限制：65535 KB
难度：4
 
描述
给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。
 
输入
第一行一个整数N(0<N<50)表示N组测试数据
接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1>V2>V3 V1<100 V3>0)表示三个水杯的体积。
第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态
输出
每行输出相应测试数据最少的倒水次数。如果达不到目标状态输出-1
样例输入
26 3 14 1 19 3 27 1 1
样例输出
3-1
来源
经典题目
上传者
hzyqazasdf


解题：BFS。。。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <ctype.h> 8 #include <cmath> 9 #include <algorithm>10 #define LL long long11 using namespace std;12 const int maxn = 100000;13 struct CUP {14     int d[3],step;15 };16 CUP cup[maxn],target,initial;17 int head,tail;18 bool vis[100][100][100];19 int bfs() {20     tail = head = 0;21     tail++;22     CUP temp,temp2;23     int t,i,j;24     while(head < tail) {25         temp = cup[head++];26         if(temp.d[0] == target.d[0] && temp.d[1] == target.d[1] && temp.d[2] == target.d[2]) {27             return temp.step;28         }29         for(i = 0; i < 3; i++) {30             for(j = 0; j < 3; j++) {31                 if((i^j) && temp.d[i] && temp.d[j] < initial.d[j]) {32                     t = min(initial.d[j] - temp.d[j],temp.d[i]);33                     temp2 = temp;34                     temp2.step++;35                     temp2.d[i] -= t;36                     temp2.d[j] += t;37                     if(!vis[temp2.d[0]][temp2.d[1]][temp2.d[2]]) {38                         vis[temp2.d[0]][temp2.d[1]][temp2.d[2]] = true;39                         cup[tail++] = temp2;40                     }41                 }42             }43         }44     }45     return -1;46 }47 int main() {48     int kase,temp,i,mx,index;49     scanf("%d",&kase);50     while(kase--) {51         mx = -1;52         for(i = 0; i < 3; i++) {53             scanf("%d",&initial.d[i]);54             if(initial.d[i] > mx) mx = initial.d[index = i];55         }56         for(i = 0; i < 3; i++)57             scanf("%d",&target.d[i]);58         memset(cup,0,sizeof(cup));59         memset(vis,false,sizeof(vis));60         cup[0].d[index] = mx;61         cup[0].step = 0;62         vis[cup[0].d[0]][cup[0].d[1]][cup[0].d[2]] = true;63         if(target.d[0] + target.d[1] + target.d[2] != mx){64             puts("-1");continue;65         }else printf("%d\n",bfs());66     }67     return 0;68 }
View Code

 

 


联系
我们